Color Length UVA

题意：输入两个长度分别为n和m的颜色序列，要求按顺序合并成同一个序列，即每次可以把一个序列开头的颜色放到新序列的尾部。对于每个颜色c来说，其跨度L（c）等于最大位置和最小位置之差，输出各颜色跨度之和。

思路：设d(i, j)表示两个序列分别移走了i和j个元素，还需要多少费用。每移一次，我们需要对已经出现但没有结束的颜色跨度加一，用数组c表示已经开始但没有结束的颜色数量，我们得到状态转移方程：dp(i,j)=min(dp(i-1,j)+c[i-1][j],dp(i,j-1)+c[i][j-1])。

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <map>

 #include <set>

 #include <unordered_map>

 #include <unordered_set>

 #include <queue>

 #include <stack>

 #include <list>

 #define FRER() freopen("in.txt", "r", stdin)

 #define FREW() freopen("out.txt", "w", stdout)

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn =  + ;

 char str[maxn], ptr[maxn];

 int ss[], sp[], es[], ep[];

 int d[maxn][maxn], c[maxn][maxn];

 int main()

 {

     ios::sync_with_stdio();

     cin.tie();

     int T;

     cin >> T;

     while(T--) {

         cin >> (str + ) >> (ptr + );

         int n = strlen(str + ), m = strlen(ptr + );

         memset(ss, INF, sizeof(ss));

         memset(sp, INF, sizeof(sp));

         memset(es, , sizeof(es));

         memset(ep, , sizeof(ep));

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

             ss[str[i] - 'A'] = min(ss[str[i] - 'A'], i);

             es[str[i] - 'A'] = i;

         }

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

             sp[ptr[i] - 'A'] = min(sp[ptr[i] - 'A'], i);

             ep[ptr[i] - 'A'] = i;

         }

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

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

                 if(!i && !j) continue;

                 int v1 = INF, v2 = INF;

                 if(i) v1 = d[i - ][j] + c[i - ][j];

                 if(j) v2 = d[i][j - ] + c[i][j - ];

                 d[i][j] = min(v1, v2);

                 if(i) {

                     c[i][j] = c[i - ][j];

                     if(ss[str[i] - 'A'] == i && sp[str[i] - 'A'] > j) c[i][j]++;

                     if(es[str[i] - 'A'] == i && ep[str[i] - 'A'] <= j) c[i][j]--;

                 }

                 else if(j) {

                     c[i][j] = c[i][j - ];

                     if(sp[ptr[j] - 'A'] == j && ss[ptr[j] - 'A'] > i) c[i][j]++;

                     if(ep[ptr[j] - 'A'] == j && es[ptr[j] - 'A'] <= i) c[i][j]--;

                 }

             }

         }

         cout << d[n][m] << endl;

     }

     return ;

 }

巴特西

Color Length UVA - 1625 DP

最新文章

热门文章