qsc54(区间dp)

题意：中文题诶～

思路：区间dp

我们可以用dp[i][j]存储区间[i, j]最少需要的打印次数，若没有相同的字母，那么需要的打印次数为dp[i+1, j]+1 (尾字符放在外层循环枚举，首字符放在内一层循环枚举，至于原因在后面会说明)。我们再枚举一个k为[i, j]的中间节点，将[i, j]分成两个子串，由子串的最优解状态转移得到当前串的最优解；那么有[i, j]被分解成[i, k], [k+1, j]，

所以有: dp[i][j]=dp[i, k] + dp[k+1][j]；若str[k]==str[j]，则dp[i, k]==dp[i+1, k] ，所以动态转移方程式为dp[i][j]=min(dp[i][j], dp[i+1][k]+dp[k+1][j])；

注意这里k>i，所以 i 必须放到内循环，不然用未更新的dp[k+1][j]去更新dp[i][j]自然是不能保证得到正确答案；其实就是枚举每个尾节点的所有情况啦。

代码：

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAXN 60

 using namespace std;

 char str[MAXN];

 int dp[MAXN][MAXN];//dp[i][j]存储区间[i,j]至少要打印多少次

 int main(void){

     while(~scanf("%s", str)){

         memset(dp, , sizeof(dp));

         int len=strlen(str);

         for(int i=; i<len; i++){//i为尾字符

             for(int j=i; j>=; j--){//j为头字符

                 dp[j][i]=dp[j+][i]+;//若没有重复的字符，那么[i,j]可以由[i+1,j]+1得到

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

                     if(str[k]==str[j]){//枚举中间字符，若str[k]==str[j],则dp[i][k]==dp[i+1][k]

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

                     }

                 }

             }

         }

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

     }

     return ;

 }

巴特西

qsc54(区间dp)

最新文章

热门文章