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

~~前置知识——区间DP~~

解题思路

1.

状态定义：

dp[l][r]

表示区间

[l,r]

能够获得的最大贡献(最大平方和)。

2.

状态转移‌

如果 $l==r$ ，即单元素区间，只能删除整个区间（如果满足 $minn <= count <= maxx$ ）。
如果不满足上述条件的话，就枚举分割点 k，将区间 $[l, r]$ 分成 $[l, k]$ 和 $[k+1, r]$ ，取两部分的最大和。于是得到 $dp[l][r]=max(dp[l][k]+dp[k+1][r])$
同时，如果区间 $[l,r]$ 的两端相同，我们可以尝试合并中间的某些部分：

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

CPP

#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;
}

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

文章操作

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

解题思路

相关推荐

评论

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