题解：P11444 [Code+#6] 祖玛

大宝和小宝 · 2025-07-16 20:25:36 · 题解

题解：P11444 [Code+#6] 祖玛

前置知识——区间DP

解题思路

• 同时，如果区间 [l,r]的两端相同，我们可以尝试合并中间的某些部分：

  例如，如果 a[l]=a[r]，我们可以先删除中间的某些部分，然后合并两端的相同元素。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<int> a(n+1);
    for (int i=1;i<=n;i++) cin>>a[i];
    int minn,maxx;
    cin>>minn>>maxx;
    vector<vector<int>>dp(n+1,vector<int>(n+1,0));
    for(int len=1;len<=n;len++) {
        for(int l=1;l+len-1<=n;l++) {
            int r=l+len-1;
            bool xt==true;
            for(int i =l+1;i<=r;++i) {
                if(a[i]!=a[l]){
                    xt=false;
                    break;
                }
            }
            if(xt&&len>=minn&&len<=maxx) dp[l][r]=len*len;
            else{
                for(int k=l;k<r;k++) dp[l][r]=max(dp[l][r],dp[l][k]+dp[k + 1][r]);
                if(a[l]==a[r]&&len>=2) {
                    for(int k=l;k<r;k++) {
                        if(dp[l][k]>0&&dp[k+1][r]>0) {
                            int lenn=(k-l+1)+(r-(k+1)+1);//区间合并后的总长度
                            if(lenn>=minn&&lenn<=maxx) dp[l][r]=max(dp[l][r],lenn*lenn);
                        }
                    }
                }
            }
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}