区间DP
惯用手段
-
区间dp中比较明显的阶段一般就是要合并的字段的长度；
-
先枚举要处理的长度，之后用短的序列求出长的即可；
P3146 248
这题长得和P3147长得一模一样
给定一个序列，每次可以合并两个相邻且相同的数，求能合并出的最大数。
区间dp和一种类倍增的写法都可以完成。
定义 \(dp_{i,j}\) 为 i 至 j 区间所能完全合并出的最大数，则当\(dp_{i,k}=dp_{i+1,k}\)有\(dp_{i,j}=dp_{i,k}+1\).
边界条件：\(dp_{i,i}=a_i\).
#include<bits/stdc++.h>
using namespace std;
int f[64][270007];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
f[x][i]=i+1;
}
int ans=0;
for(int i=2;i<=58;i++){
for(int j=1;j<=n;j++){
if(!f[i][j])
f[i][j]=f[i-1][f[i-1][j]];
if(f[i][j])
ans=i;
}
}
cout<<ans<<endl;
}
CF607B 祖玛
给定一个序列，每次可以删除其中的一个回文串（剩余部分会拼起来），求把整个序列删除的时间。
验证一个回文串的方法可以参照P1435 回文子串。我们定义 \(f_{i,j}\) 为将i到j的子段完全消去所用的次数。
考虑一个较长的子段是如何由短子段转移而来的：
1.子串本身就是回文串 可以直接按照回文子串的方式判定；
2.子串由两个回文串拼接而成，如：abacdc ，此时需要枚举中间划分的点k；
3.子串为“大串套小串”也就是 a dcd bba 这种形式，注意到这种情况不需要单独讨论，因为 该子串可以由 dcd bb 这个由两个回文串拼成的子串转移而来，再按照 1 中的规则转移即可；
P5189双倍经验
#include<iostream>
using namespace std;
int f[5005][5005];
int n,a[5005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
f[i][i]=1;
}
for(int i=1;i<=n-1;i++){
if(a[i]==a[i+1])f[i][i+1]=1;
else f[i][i+1]=2;
}
for(int l=2;l<n;l++){
for(int i=1;i<=n-l;i++){
int j=i+l;
f[i][j]=114514;
if(a[i]==a[j])f[i][j]=f[i+1][j-1];
for(int k=i;k<j;k++){
f[i][j]=min(f[i][k]+f[k+1][j],f[i][j]);
}
}
}
cout<<f[1][n];
}
P5189 ZUMA
并不是双倍经验呜呜呜
给点一个序列，每次可以在其中插入一个数，相同连续长度超过k子段会消失，求插入数的个数。
一样的思路，试图将插入分成两类，从头插入和从中间插。直接挪用上题中的状态是不行的>_<
因为需要连续相同字段的长度大于等于k，出现了更为复杂的状态，此时可以考虑把状态加上一维，
定义\(f_{i,j,k}\) 为将 i j 一段完全消除所需要的彩珠数，同时 i 前有 k 个和 i 颜色相同的彩珠。
转移的方法就和上一题差不多了，详见代码:
#include<bits/stdc++.h>
using namespace std;
int f[105][105][5];
int a[105];
int main(){
memset(f, 0x3f, sizeof(f));
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<k;j++){
f[i][i][j]=k-j-1;//为什么是k-j-1？因为显然要消去一个数，它左边和它相等的数越少越好，如果本来就有很多数与其相等，那么付出的代价也会少很多
}
}
for(int l=1;l<n;l++){
for(int i=1;i<=n-l;i++){
int j=i+l;
for(int c=k-1;c>=0;c--){
if(c==k-1)
f[i][j][c]=min(f[i][j][c],f[i+1][j][0]);
else if(c<k-1)
f[i][j][c]=min(f[i][j][c],f[i][j][c+1]+1); //如果多一颗的话就需要更少的彩珠
if(a[i]==a[i+1])
f[i][j][c]=min(f[i][j][c],f[i+1][j][min(k-1,c+1)]);
for(int g=i+1;g<=j-1;g++){
if(a[i]==a[g+1])
f[i][j][c]=min(f[i][j][c],f[i+1][g][0]+f[g+1][j][min(k-1,c+1)]);
}
}
}
}
cout<<f[1][n][0]<<endl;
}