快速网站开发介绍,wordpress 分类 模板,电子 公司 网站建设,北京专业网站制作服务标准String painter HDU - 2476 题意#xff1a; 我认为这是一道比较难的问题#xff0c;自己想了很久#xff0c;没有想出来怎么做#xff0c;可能是因为思维僵化吧#xff0c;一直在想怎么直接的由A变到B#xff0c;事实上#xff0c;可以有中间桥梁连接A和B#xff0c;… String painter HDU - 2476 题意 我认为这是一道比较难的问题自己想了很久没有想出来怎么做可能是因为思维僵化吧一直在想怎么直接的由A变到B事实上可以有中间桥梁连接A和B他们之间的关系可能往往没有我们想的那么简单。
依最简单的思路我们定义ans[i]代表区间[1...i]处A直接变到B所需的最少次数。那么状态转移方程可以这样写
有几种情况
1如果strA[i] strB[i]的话那么存在着一个转移方程就是 ans[i] min(ans[i],ans[i-1]);
2否则的话那么第i个位置的字符一定会被刷掉此外刷掉第i个位置的区间长度可能大于1假设这个区间刷掉了区间[x,i]内的数并把区间strA[x...i]内的数都刷成了strB[i]
这样的话就相当于把区间[x...i]由空白串直接变成strB[x...i]剩下的区间[1...x-1]可以用ans[x-1]转移过来
也就是说转移方程写成ans[i] min(ans[i],ans[x-1] dp[x][i])dp[x][i]表示从空白串直接变成strB[x][i]所需要用的最小次数。
下面我们的重要目标就是求出dp[i][j]来
其实到这里还是不太好想。
最右边的字符strB[j]一定是最先被刷出来的
1如果strB[i] strA[j],那么在一开始刷刷出strB[j]的时候顺手就可以把strB[i]也给刷出来所以不需要额外的费用
dp[i][j] dp[i1][j]
2然后我们把区间分成两块进行转移非常常规的想法
dp[i][j] min(dp[i][j],dp[i][k]dp[k1][j]); 代码注意我在前面的区间写的是全闭而在代码里的区间写法是左闭右开 #include iostream
#include cstring
#include cstdio
#include algorithm
using namespace std;
const int MAX 106;
char strA[MAX];
char strB[MAX];
int dp[MAX][MAX];
int ans[MAX];
int n;
int main(){while(scanf(%s %s,strA,strB) ! EOF){memset(dp,0,sizeof(dp));memset(ans,0,sizeof(ans));n strlen(strA);for(int i 0;i n;i) dp[i][i1] 1;for(int len 2;len n;len){for(int i 0;i len n;i){dp[i][ilen] dp[i1][ilen] (strB[i] strB[ilen-1]?0:1);for(int j i1;j ilen;j){dp[i][ilen] min(dp[i][ilen],dp[i][j]dp[j][ilen]);} }}ans[0] strA[0] strB[0] ? 0:1;for(int i 1;i n;i){ans[i] dp[0][i1];if(strB[i] strA[i])ans[i] min(ans[i],ans[i-1]);for(int j 0;j i;j){ans[i] min(ans[i],ans[j] dp[j1][i1]);}}coutans[n-1]endl;}return 0;
}
