/*
区间dp，为什么要升维？
因为若用dp[l][r]表示消去dp[l][r]的最大的分，那么显然状态转移方程dp[l][r]=max{dp[l+1][k-1]+(len[l]+len[k])^2+len[k+1][r]}
可是这样是直接消去l和k两个快的，有一种情况是在k.r两个块之间还有个同色块，那么这种情况就考虑不到了
所以我们要考虑是否能先不直接消去l,k合并的块，而是将其保留下来,之后枚举到k,r区域的块时再一同合并进行考虑
所以再加一维来记录l,k合并后的信息
为了方便，再加一维来表示r后面的同色块情况
dp[l][r][q]表示区间消去区间[l,r]并且区间右侧有长度为q的和块r颜色相同的块，所得到的分数
此时有两种情况
1：r和len合并，直接消去
dp[l][r][q]=dp[l][r-1][0]+(len[r]+q)^2;
2: r和len合并，并且和[l,r-1]中的k块合并
dp[l][r][q]=max{dp[l][k][len[j]+q]+dp[k+1][r-1][0]}
两种情况取最大值即可
初始化状态dp[i][i]=1，目标状态dp[1][m][0]
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 220
int n,m,a[maxn],color[maxn],len[maxn],dp[maxn][maxn][maxn];
int dfs(
int l,
int r,
int q){
if(dp[l][r][q]!=-
1)
return dp[l][r][q];
if(l==r)
return dp[l][r][q]=(len[r]+q)*(len[r]+
q);
int Max=(len[r]+q)*(len[r]+
q);
Max+=dfs(l,r-
1,
0);
//第一种情况
for(
int k=l;k<r;k++
)
if(color[k]==color[r]) Max=max(Max,dfs(l,k,q+len[r])+dfs(k+
1,r-
1,
0));
//printf("%d %d %d %d\n",l,r,q,Max);
return dp[l][r][q]=
Max;
}
int main(){
int t;
cin>>
t;
for(
int tt=
1;tt<=t;tt++
){
printf("Case %d: ",tt);
cin>>
n;
for(
int i=
1;i<=n;i++)cin>>
a[i];
int last=a[
1];
m=
1,color[
1]=a[
1],len[
1]=
1;
for(
int i=
2;i<=n;i++){
//把颜色小块合并成大块
if(a[i]==last)len[m]++
;
else {
last=a[i];color[++m]=a[i];len[m]=
1;
}
}
memset(dp,-
1,
sizeof dp);
dfs(1,m,
0);
printf("%d\n",dp[
1][m][
0]);
}
}
cf的题
/*
dp[l][r][q]表示消去区间[l,r]+q的最大值
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200
ll n,dp[maxn][maxn][maxn],c[maxn],len[maxn];
char s[maxn];
ll dfs(int l,
int r,
int q){
if(l>r)
return 0;
if(l==r)
return len[
1+
q];
if(~dp[l][r][q])
return dp[l][r][q];
ll Max=dfs(l,r-
1,
0)+len[
1+
q];
for(
int k=l;k<r;k++
)
if(s[r]==s[k])Max=max(Max,dfs(l,k,q+
1)+dfs(k+
1,r-
1,
0));
//printf("%d %d %d %d\n",l,r,q,Max);
return dp[l][r][q]=
Max;
}
int main(){
cin>>
n;
scanf("%s",s);
for(
int i=
1;i<=n;i++)cin>>
len[i];
memset(dp,-
1,
sizeof dp);
printf("%lld\n",dfs(
0,n-
1,
0));
}
转载于:https://www.cnblogs.com/zsben991126/p/10328071.html
