/* 区间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 ",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 ",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 ",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 ",dfs(0,n-1,0)); }