首页 > 代码库 > HDU 5903 - Square Distance [ DP ] ( BestCoder Round #87 1002 )

HDU 5903 - Square Distance [ DP ] ( BestCoder Round #87 1002 )

2024-08-14 16:57:46   224人阅读

题意：   

　　给一个字符串t ，求与这个序列刚好有m个位置字符不同的由两个相同的串拼接起来的字符串 s，   

　　要求字典序最小的答案
    
分析：   

　　dp[i][j] 表示 第i位及之后的总代价为j可不可行   

　　从第 n/2-1 位推回第 0 位， 若dp[0][m] = 1，则存在   

　　然后贪心对每一位从‘a‘试到‘z‘，选取接下来存在解的字符

 

 1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 const int MAXN = 1005; 7 bool dp[MAXN][MAXN];//dp[i][j] ：第i位及之后的总代价为j可不可行  8 int t, n, m; 9 char s[MAXN];10 int main()11 {12     scanf("%d", &t);13     while (t--)14     {15         scanf("%d%d", &n, &m);16         scanf("%s", s);17         memset(dp, 0, sizeof(dp));18         dp[n/2][0] = 1;19         for (int i = n/2-1; i >= 0; i--)20         {21             if (s[i] == s[i+n/2])22             {23                 for (int j = 0; j <= m; j++) dp[i][j] = dp[i+1][j];//不改24                 for (int j = 0; j <= m-2; j++) if (dp[i+1][j]) dp[i][j+2] = 1;//改两个25             }26             else27             {28                 for (int j = 0; j <= m-1; j++) if (dp[i+1][j]) dp[i][j+1] = 1;//改一个29                 for (int j = 0; j <= m-2; j++) if (dp[i+1][j]) dp[i][j+2] = 1;//改两个30             }31         }32         if (!dp[0][m])33         {34             puts("Impossible"); continue;35         }36         int k = m;37         for (int i = 0; i < n/2; i++)38         {39             for (int j = 0; j < 26; j++)40             {41                 int p = 0;42                 if (s[i] != j+‘a‘) p++;43                 if (s[i+n/2] != j+‘a‘) p++;44                 if (dp[i+1][k-p])45                 {46                     s[i] = j + ‘a‘;47                     s[i+n/2] = j + ‘a‘;48                     k -= p;49                     break;50                 }51             }52         }53         puts(s);54     }55 }

 

HDU 5903 - Square Distance [ DP ] ( BestCoder Round #87 1002 )


联系
我们