首页 > 代码库 > hdu_5903_Square Distance(dp)
hdu_5903_Square Distance(dp)
题目链接：hdu_5903_Square Distance
题意：
给你一个长度为n的a串，一个数m，现在让你构造一个长度也为n的b串，使这个串是由两个相同的串拼起来的，并且和a串对应的位不同的数量为m
题解：
1.可以知道构造的串前面和后面都是相同的，所以只需要构造前半段就行了，当然你可以分类讨论，然后构造
2.设dp[i][j]表示考虑到第i个字符已经有j个与a串对应位不同，然后状态转移方程看代码，注意的是这里要倒着转移回去
因为要满足最小的字典序，并且对应不同的位数为m，倒着转移构造m，最后正着改变字符
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 5 const int N=1007; 6 int t,n,m; 7 bool dp[N][N]; 8 char s[N]; 9 10 void O_O()11 {12 int haf=n/2;13 F(i,0,haf+1)F(j,0,m)dp[i][j]=0;14 dp[haf+1][0]=1;15 for(int i=haf;i>=1;i--)if(s[i]==s[haf+i])16 {17 F(j,0,m)dp[i][j]|=dp[i+1][j];//不改18 F(j,2,m)dp[i][j]|=dp[i+1][j-2];//改两个19 }else20 {21 F(j,1,m)dp[i][j]|=dp[i+1][j-1];//改一个22 F(j,2,m)dp[i][j]|=dp[i+1][j-2];//改两个23 }24 if(!dp[1][m]){puts("Impossible");return;}25 F(i,1,haf)F(j,0,25)26 {27 int now=(s[i]!=j+‘a‘)+(s[i+haf]!=j+‘a‘);28 if(dp[i+1][m-now])29 {30 s[i+haf]=s[i]=j+‘a‘,m-=now;31 break;32 }33 }34 puts(s+1);35 }36 37 int main()38 {39 scanf("%d",&t);40 while(t--)scanf("%d%d%s",&n,&m,s+1),O_O();41 return 0;42 }
hdu_5903_Square Distance(dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。