UVA 1625 "Color Length" （基础DP）

传送门

•参考资料

　　[1]:HopeForBetter

•题意

　　

•题解（by 紫书）

　　

•我的理解

　　用了一上午的时间，参考紫书+上述博文，终于解决了疑惑；

　　定义第一个颜色序列用串 s 表示，第二个用串 t 表示，下标均从 1 开始；

　　定义dp(i,j)表示串 s 的前 i 个字符与串 t 的前 j 个字符合并的最小值；

　　' ? ' 是加什么呢？

　　分析一下，当前的新序列包含哪些类型的字符：

　　1)当前新序列包含字符 ch 的开始和结束；

　　2)当前新序列只包含字符 ch 的开始，而不包含其结束；

　　3)当前新序列不包含字符 ch；

　　就情况①，将 s_i 插入到尾部后，你会发现，这个新插入的元素只会影响 1) 类型字符，怎么影响呢？

　　当前字符 si 的插入会使得 1) 类型的字符首尾距离增加 1；

　　那么，情况①中的 ' ? ' 指的就是 s 串的前 i-1 个字符与 t 串中的前 j 个字符的 1) 类型的字符个数；

　　情况②同理；

　　那么，如何求解 "s 串的前 i-1 个字符与 t 串中的前 j 个字符的 1) 类型的字符个数" 呢？

　　定义 w(i,j) 表示串 s 的前 i 个字符与串 t 的前 j 个字符包含的 1) 类型的字符总个数；

 struct Data

 {

     int fir,las;

     Data(int fir=INF,int las=):fir(fir),las(las){}

 };

 int w[maxn][maxn];

 void Preset()

 {

     /**

         a[i].fir:字符 'A'+i 在串s中第一次出现的位置

         a[i].las:字符 'A'+i 在串s中最后一次出现的位置

         b[i].fir:字符 'A'+i 在串t中第一次出现的位置

         b[i].las:字符 'A'+i 在串t中最后一次出现的位置

     */

     Data a[],b[];

     for(int i=;i <= n;++i)

     {

         Data &tmp=a[s[i]-'A'];

         tmp.fir=min(tmp.fir,i);

         tmp.las=i;

     }

     for(int i=;i <= m;++i)

     {

         Data &tmp=b[t[i]-'A'];

         tmp.fir=min(tmp.fir,i);

         tmp.las=i;

     }

     w[][]=;

     for(int i=;i <= n;++i)

     {

         for(int j=;j <= m;++j)

         {

             if(i)

             {

                 w[i][j]=w[i-][j];

                 int k=s[i]-'A';

                 if(a[k].fir == i && b[k].fir > j)///判断si是否为首次出现的

                     w[i][j]++;

                 if(a[k].las == i && b[k].las <= j)///判断si是否为结尾字符

                     w[i][j]--;

             }

             if(j)

             {

                 w[i][j]=w[i][j-];

                 int k=t[j]-'A';

                 if(b[k].fir == j && a[k].fir > i)///判断tj是否为首次出现的

                     w[i][j]++;

                 if(b[k].las == j && a[k].las <= i)///判断tj是否为结尾字符

                     w[i][j]--;

             }

         }

     }

 }

求解w(i,j)

　　求解完 w(i,j) 后，状态转移方程也就完成了：

•Code

 #include<bits/stdc++.h>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define INFll 0x3f3f3f3f3f3f3f3f

 #define ll long long

 const int maxn=5e3+;

 int n,m;

 char s[maxn];

 char t[maxn];

 struct Data

 {

     int fir,las;

     Data(int fir=INF,int las=):fir(fir),las(las){}

 };

 int w[maxn][maxn];

 ll dp[maxn][maxn];

 void Preset()

 {

     /**

         a[i].fir:字符 'A'+i 在串s中第一次出现的位置

         a[i].las:字符 'A'+i 在串s中最后一次出现的位置

         b[i].fir:字符 'A'+i 在串t中第一次出现的位置

         b[i].las:字符 'A'+i 在串t中最后一次出现的位置

     */

     Data a[],b[];

     for(int i=;i <= n;++i)

     {

         Data &tmp=a[s[i]-'A'];

         tmp.fir=min(tmp.fir,i);

         tmp.las=i;

     }

     for(int i=;i <= m;++i)

     {

         Data &tmp=b[t[i]-'A'];

         tmp.fir=min(tmp.fir,i);

         tmp.las=i;

     }

     w[][]=;

     for(int i=;i <= n;++i)

     {

         for(int j=;j <= m;++j)

         {

             if(i)

             {

                 w[i][j]=w[i-][j];

                 int k=s[i]-'A';

                 if(a[k].fir == i && b[k].fir > j)///判断si是否为首次出现的

                     w[i][j]++;

                 if(a[k].las == i && b[k].las <= j)///判断si是否为结尾字符

                     w[i][j]--;

             }

             if(j)

             {

                 w[i][j]=w[i][j-];

                 int k=t[j]-'A';

                 if(b[k].fir == j && a[k].fir > i)///判断tj是否为首次出现的

                     w[i][j]++;

                 if(b[k].las == j && a[k].las <= i)///判断tj是否为结尾字符

                     w[i][j]--;

             }

         }

     }

 }

 ll Solve()

 {

     Preset();

     dp[][]=;

     for(int i=;i <= n;++i)

     {

         for(int j=;j <= m;++j)

         {

             if(!(i+j))

                 continue;

             dp[i][j]=INFll;

             if(i)

                 dp[i][j]=min(dp[i][j],dp[i-][j]+w[i-][j]);

             if(j)

                 dp[i][j]=min(dp[i][j],dp[i][j-]+w[i][j-]);

         }

     }

     return dp[n][m];

 }

 int main()

 {

     int test;

     scanf("%d",&test);

     while(test--)

     {

         scanf("%s%s",s+,t+);

         n=strlen(s+);

         m=strlen(t+);

         printf("%lld\n",Solve());

     }

     return ;

 }

巴特西

UVA 1625 "Color Length" （基础DP）

•参考资料

•题意

•题解（by 紫书）

•我的理解

•Code

最新文章

热门文章