上海计算机学会2024年7月月赛C++乙组T4修改回文（二）

 #include<bits/stdc++.h>

    
 using namespace std;
    
 //dp[i][j]为从i开头到j结尾添加字符后的最小回文串
    
 //为节省空间，将i为奇数存入dp[1][j],偶数存入dp[0][j];
    
 string dp[2][3005];
    
 string s;
    
 int len;//字符串长度
    
 int main() {
    
     cin >> s;
    
     len = s.length();
    
     for(int i = len - 1; i >= 0; i--) {//枚举所有开头为i，结尾为j的子串
    
     for(int j = i; j < len; j++) {
    
         if (i == j) {//单个字符，自己即为回文串
    
             dp[i % 2][j] = s[i];
    
         } else if (s[i] == s[j]) {//头尾相同，都加头或尾
    
             dp[i % 2][j] = s[i] + dp[(i + 1) % 2][j - 1] + s[j];
    
         } else {//头尾不同
    
             //都加头
    
             string t1 = s[i] + dp[(i + 1) % 2][j] + s[i];
    
             //都加尾
    
             string t2 = s[j] + dp[i % 2][j - 1] + s[j];
    
             //取最小值
    
             if (t1.length() > t2.length()) {
    
                 dp[i % 2][j] = t2;
    
             } else if (t1.length() < t2.length()) {
    
                 dp[i % 2][j] = t1;
    
             } else {
    
                 dp[i % 2][j] = min(t1, t2);
    
             }
    
         }
    
     }
    
     }
    
     cout << dp[0][len - 1];
    
     return 0;
    
 }