Uva 11552 Fewest Flops (三维动态规划)

dp[l][i][j] 表示第l个分组以第i个字母组开头以第j个字母组结尾时候最小划分的块数

n=strlen(S)/k

dp[l][i][j] 的值分两种情况：

1.头i在第l-1组中在位置h找到了，说明头尾可以相接，那么遍历l-1组中以h结尾的所有值，求得最小值temp:

dp[l][i][j]=temp+strlen(ss[l])-1;

2.没找到，那么遍历l-1组中的所有值，求得最小值temp:

if(dp[l][i][j]>temp+strlen(ss[l]))dp[l][i][j]=temp+strlen(ss[l]);

最后遍历dp[n-1][i][j]求得最小值即可。

此题千万要仔细，太麻烦了。

#include <iostream>#include <cstring>#include <string>using namespace std;int k,dp[1005][30][30];char ss[1005][1005],s[1005];void juhe(int h,int i,int j) //对【i,j)这个块去重{int bz[27],l=0; memset(bz,0,sizeof(bz));for(;i<j;i++)if(bz[s[i]-'a']==0) {ss[h][l++]=s[i];bz[s[i]-'a']=1;}ss[h][l]=0;//cout<<ss[h]<<" "<<strlen(ss[h])<<endl; }int search_i(int l,int i) //在ss[l-1]中查找ss[l][i] {for(int j=0;j<strlen(ss[l-1]);j++)if(ss[l][i]==ss[l-1][j]) return j;return -1;}int main(int argc, char *argv[]){int i,j,l,t,n,ans;cin>>t;while(t--){cin>>k>>s; n=strlen(s)/k;for(i=0;i<n;i++){juhe(i,i*k,(i+1)*k);}for(l=0;l<n;l++){for(i=0;i<strlen(ss[l]);i++){for(j=0;j<strlen(ss[l]);j++){   if(i!=j||(strlen(ss[l])==1)) //头和尾是不能相同的，除非长度为1 {if(l==0) dp[l][i][j]=strlen(ss[l]); else //两种情况,取小的 {   int h=search_i(l,i),temp;dp[l][i][j]=10000;if(h>=0)//找到匹配，遍历第l-1组中以h结尾的值，得到min {   temp=10000;for(int g=0;g<strlen(ss[l-1]);g++)if(dp[l-1][g][h]<temp) temp=dp[l-1][g][h];dp[l][i][j]=temp+strlen(ss[l])-1;}   //没有匹配的，遍历第l-1组中所有的值，得到min temp=10000;for(int p=0;p<strlen(ss[l-1]);p++)for(int q=0;q<strlen(ss[l-1]);q++)if(dp[l-1][p][q]<temp) temp=dp[l-1][p][q];if(dp[l][i][j]>temp+strlen(ss[l])) dp[l][i][j]=temp+strlen(ss[l]);}}else dp[l][i][j]=10000; }}}for(ans=10000,i=0;i<strlen(ss[n-1]);i++)for(j=0;j<strlen(ss[n-1]);j++)if(dp[n-1][i][j]<ans) ans=dp[n-1][i][j];cout<<ans<<endl;}return 0;}