UVA Live Archive 4394 String painter（区间dp）

区间dp，两个str一起考虑很难转移。

看了别人题解以后才知道是做两次dp。

dp1。str1最坏情况下和str2完全不相同，相当于从空白串开始刷。

对于一个区间，有两种刷法，一起刷，或者分开来刷。

规定[i][i-1]为空串，这样一起刷可以归结为第二种情况。

合并的时候，大的区间的次数<=小的区间的，和新加入区间的字符有关。

小的区间是一个字符一个字符的变成大区间的。

所以每次考虑新加入区间的尾部字符j，枚举k划分区间[i][k-1]，[k][j]。

要使得刷的次数减少，只有尽量一起刷。比如aba，aa，abcda。

当s[k] == s[j]的时候可以先刷一遍[i,j]然后刷中间，等效于dp[k][j-1]。

dp2。得出最坏的情况以后。dp2[i]表示以i结尾的子串的最优解。

然后考虑结尾s[i]和t[i]的关系。

#include<bits/stdc++.h>

using namespace std;

const int LEN = ;

char s[LEN], t[LEN];

int dp[LEN][LEN];

int dp2[LEN];

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    while(gets(s)){

        gets(t);

        int len = strlen(t);

        for(int d = ; d < len; d++){

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

                int j = i+d; //每次只考虑新加入区间的j

                dp[i][j] = dp[i][j-] + ; //单刷

                for(int k = i; k < j; k++){//划分区间，[i,k-1] [k,j]分开来刷  [i][i-1]表示为空

                    if(t[k-] == t[j-]){ // dp[i][j-1] <= dp[i][k-1]+dp[k][j-1]，所以只有t[k-1] == t[j-1]才可能有更优的解

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

                    }

                }

            }

        }

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

            if(s[i-] == t[i-]) dp2[i] = dp2[i-]; //新的这个可以不刷

            else { //不等则划分

                dp2[i] = i;

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

                    dp2[i] = min(dp2[i],dp2[k]+dp[k+][i]);

                }

            }

        }

        printf("%d\n",dp2[len]);

    }

    return ;

}

巴特西

UVA Live Archive 4394 String painter（区间dp）

最新文章

热门文章