本文共 2022 字,大约阅读时间需要 6 分钟。
1、
2、题目大意:
有两个字符串长度相同,现在有一个painter,一次可以把第一个字符串中的一段区间内的所有字母都换成同一个字母(这个字母可以是任意一个),问最少执行多少次操作,才能将第一个字符串转换成第二个字符串
3、解题思路:
dp[i][j]表示i-j区间内的最少次数
先操作第二个字符串,我们先假设第i个字符的位置需要喷刷一次,对于所有的dp[i][j]=dp[i+1][j]+1、
在i-j区间内,如果有第k个跟第i个相同,那么就可以将i-j区间借助k分成两部分dp[i][j]=min(dp[i+1][k]+dp[k+1][j]);
处理完第2个字符串后,我们就要看第一个字符串究竟需要喷刷多少次了,用ans[i]记录0-i区间第二个字符串得出的喷刷次数,如果第一个字符串的i位置与第二个字符串的i位置相同,那么这个位置就不用喷刷了,ans[i]=ans[i-1],如果不相同,就要就要借助一个位于o-i区间内的变量来分割开
4、题目:
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1365 Accepted Submission(s): 585
zzzzzfzzzzzabcdefedcbaababababababcdcdcdcdcdcd
67
5、AC代码:
#include#include #include using namespace std;#define N 105char s1[N],s2[N];int dp[N][N];int ans[N];int main(){ while(scanf("%s%s",s1,s2)!=EOF) { int len=strlen(s1); memset(dp,0,sizeof(dp)); for(int j=0; j =0; i--) { dp[i][j]=dp[i+1][j]+1; for(int k=i+1; k<=j; k++) { if(s2[i]==s2[k]) dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]); } } } for(int i=0; i
转载地址:http://qgddi.baihongyu.com/