区间DP复习
(难度排序：(A,B),(F,G,E,D,H,I,K),(C),(J,L))
这是一个基本全在bzoj上的复习专题
没有什么可以说的，都是一些基本的dp思想
A [BZOJ1996] [Hnoi2010] chorus 合唱队
裸题
\(dp[i][j][2]\)表示区间\(i,j\)最后放的是\(i\)还是\(j\)的方案数
int n;
int a[N];
ll dp[N][N][2];
int main(){
rep(i,1,n=rd()) a[i]=rd();
rep(i,1,n) dp[i][i][0]=1;
drep(i,n,1) rep(j,i,n) rep(k,0,1) {
if(k==0) {
if(i>1 && a[i-1]<a[i]) (dp[i-1][j][0]+=dp[i][j][k])%=P;
if(j<n && a[j+1]>a[i]) (dp[i][j+1][1]+=dp[i][j][k])%=P;
} else {
if(i>1 && a[i-1]<a[j]) (dp[i-1][j][0]+=dp[i][j][k])%=P;
if(j<n && a[j+1]>a[j]) (dp[i][j+1][1]+=dp[i][j][k])%=P;
}
}
cout<<(dp[1][n][0]+dp[1][n][1])%P<<endl;
}
\[\
\]
\[\
\]
B [BZOJ1055] [HAOI2008] 玩具取名
\(dp[i][j][4]\)表示\(i,j\)这段区间能否变成四个字母
int n;
int ch[N];
char c[]="WING";
char s[N];
int can[5][5][5];
int dp[N][N][4];
int main(){
int a=rd(),b=rd(),c=rd(),d=rd();
rep(i,0,3) ch[(int)::c[i]]=i;
rep(i,1,a) {
scanf("%s",s);
can[ch[(int)s[0]]][ch[(int)s[1]]][0]=1;
}
rep(i,1,b) {
scanf("%s",s);
can[ch[(int)s[0]]][ch[(int)s[1]]][1]=1;
}
rep(i,1,c) {
scanf("%s",s);
can[ch[(int)s[0]]][ch[(int)s[1]]][2]=1;
}
rep(i,1,d) {
scanf("%s",s);
can[ch[(int)s[0]]][ch[(int)s[1]]][3]=1;
}
scanf("%s",s+1);
n=strlen(s+1);
rep(i,1,n) dp[i][i][ch[(int)s[i]]]=1;
drep(i,n,1) rep(j,i,n) {
rep(k,i,j-1) {
rep(o,0,3) rep(a,0,3) rep(b,0,3) dp[i][j][o]|=(dp[i][k][a]&&dp[k+1][j][b]&&can[a][b][o]);
}
}
int f=0;
rep(i,0,3) if(dp[1][n][i]) cout<<::c[i],f=1;
if(!f) puts("The name is wrong!");
}
关于代码里这个::前缀，它是用来访问main函数外的东西
\[\
\]
\[\
\]
C 方块消除
题目描述
Jimmy最近迷上了一款叫做方块消除的游戏。游戏规则如下：nn个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻方块颜色相同，则这两个方块属于同一区域。游戏时，你可以任选一个区域消去。设这个区域包含的方块数为xx，则将得到x2x2个分值。方块消去之后，其右边的所有方块就会向左移。虽然游戏很简单，但是要拿高分也很不容易。Jimmy希望你能找出得最高分的最佳方案，你能帮助他吗？
输入
第一行包含一个整数n(0<=n<=200)，表示方块数目。第二行包含n个数，表示每个方块的颜色（1到n之间的整数）。
输出
仅一个整数，即最高可能得分。
这个题据说是有\(O(n^3)\)的解法的，但是由于能力有限，我只能提供\(O(n^4)\)做法
首先要把连续的段压缩
\(dp[i][j][k]\)表示\(i,j\)这段区间，消完还剩下\(k\)个颜色为\(a[j]\)的块的最大答案
注意，直接令颜色为端点的转移很常见，这样是可以转移到所有方案的
每次枚举一个\(d\)
若\(a[d]=a[j]\)，就可以把\(d+1,j\)这一段与\(i,d\)写一个类似背包的转移
当然还有直接合并的转移
const int N=219;
template <class T> void chk(T &a,T b){ ((a<b)&&(a=b)); }
int n;
int a[N],b[N],c[N],cnt;
int dp[N][N][N];
int s[N];
int main(){
rep(i,1,n=rd()) a[i]=rd();
rep(i,1,n) if(a[i]!=a[i-1]) {
cnt++;
b[cnt]=a[i];
c[cnt]=1;
} else c[cnt]++;
rep(i,1,n=cnt) s[i]=s[i-1]+c[i];
memset(dp,-10,sizeof dp);
rep(i,1,n) dp[i][i][0]=c[i]*c[i],dp[i][i][c[i]]=0;
drep(i,n,1) {
rep(j,i,n) {
chk(dp[i][j][c[j]],dp[i][j-1][0]);
rep(k,i,j-1) {
if(b[k]==b[j])
rep(o,c[j],s[j]-s[i-1])
chk(dp[i][j][o],dp[i][k][o-c[j]]+dp[k+1][j][c[j]]);//类似背包的转移
chk(dp[i][j][0],dp[i][k][0]+dp[k+1][j][0]);//直接合并
}
rep(k,0,s[j]-s[i-1]) chk(dp[i][j][0],dp[i][j][k]+k*k);
}
}
printf("%d\n",dp[1][n][0]);
}
\[\
\]
\[\
\]
D [BZOJ1068] [SCOI2007]压缩
这题数据范围小，转移的时候直接暴力check就行了
我写的比较奇怪，不建议参考
int n,m;
char s[N];
int dp[N][N][2];
int Check(int l1,int r1,int l2,int r2) {
if(r1-l1!=r2-l2) return false;
rep(i,0,r1-l1) if(s[l1+i]!=s[l2+i]) return false;
return true;
}
inline void chk(int &a,int b){ ((a>b)&&(a=b)); }
int main(){
scanf("%s",s+1);
n=strlen(s+1);
memset(dp,10,sizeof dp);
rep(i,1,n) dp[i][i][0]=1,dp[i][i][1]=2;
drep(i,n,1) {
rep(j,i,n) {
chk(dp[i][j][0],j-i+1);
chk(dp[i][j][1],j-i+2);
rep(k,i,j-1) {
chk(dp[i][j][0],min(dp[i][k][0],(dp[i][k][1]-(i==1)))+min(dp[k+1][j][0],dp[k+1][j][1]));
if(Check(i,k,k+1,j)) {
chk(dp[i][j][1],dp[i][k][1]+1);
}
chk(dp[i][j][1],dp[i][k][1]+j-k);
}
chk(dp[i][j][0],dp[i][j][1]);
}
}
int ans=min(dp[1][n][0],dp[1][n][1]-1);
printf("%d\n",ans);
}
\[\
\]
\[\
\]
E [BZOJ1090] [SCOI2003]字符串折叠
同上一题
const int N=110,P=19650827;
inline void chk(int &a,int b){ ((a>b)&&(a=b)); }
int n;
char s[N];
int dp[N][N];
int cnt[N];
int Check(int l,int r,int t) {
int len=r-l+1;
rep(i,0,t-1) {
rep(j,0,len/t-1) {
if(s[l+i+t*j]!=s[l+i]) return false;
}
}
return true;
}
int main(){
rep(i,1,N-1) cnt[i]=cnt[i/10]+1;
scanf("%s",s+1);
n=strlen(s+1);
memset(dp,10,sizeof dp);
rep(i,1,n) dp[i][i]=1;
drep(i,n,1) {
rep(j,i,n) {
rep(k,i,j-1) chk(dp[i][j],dp[i][k]+dp[k+1][j]);
int len=j-i+1;
for(reg int k=1;k<=len;++k)
if(len%k==0)
if(Check(i,j,k)) chk(dp[i][j],dp[i][i+k-1]+2+cnt[len/k]);
}
}
printf("%d\n",dp[1][n]);
}
\[\
\]
\[\
\]
F [BZOJ1260] [CQOI2007]涂色paint
\(dp[i][j][k]\)表示\(i,j\)这段区间涂完之后还剩下颜色\(k\)
转移时同色合并即可
const int N=51,P=19650827;
inline void chk(int &a,int b){ ((a>b)&&(a=b)); }
int n;
char s[N];
int a[N];
int dp[N][N][27];
int ch[N];
int main(){
scanf("%s",s+1);
rep(i,1,n=strlen(s+1)) a[i]=s[i]-'A'+1;
memset(dp,10,sizeof dp);
rep(i,1,n) dp[i][i][a[i]]=0;
drep(i,n,1) rep(j,i,n) {
rep(k,i,j-1) rep(o,1,26) chk(dp[i][j][o],dp[i][k][o]+dp[k+1][j][o]);
rep(k,1,26) chk(dp[i][j][0],dp[i][j][k]+1);
rep(k,1,26) chk(dp[i][j][k],dp[i][j][0]);
}
printf("%d\n",dp[1][n][0]);
}
\[\
\]
\[\
\]
G [BZOJ1261] [SCOI2006]zh_tree
这题不用输出方案的。。。
直接对于前序遍历dp
template <typename T> void chk(T &a,T b){ if(a>b) a=b; }
int n;
double k,c,a[N];
double dp[N][N];
int main(){
scanf("%d%lf%lf",&n,&k,&c);
int s=0;
rep(i,1,n) s+=(a[i]=rd());
rep(i,1,n) a[i]=a[i]/s;
rep(i,1,n) dp[i][i]=a[i];
rep(i,1,n) a[i]+=a[i-1];
drep(i,n,1) rep(j,i+1,n) {
dp[i][j]=1e18;
rep(k,i,j) chk(dp[i][j],dp[i][k-1]+dp[k+1][j]+a[j]-a[i-1]);
}
printf("%.3lf\n",dp[1][n]*k+c);
}
\[\
\]
\[\
\]
H,I [BZOJ1694] [Usaco2007 Demo]Grazing on the Run
首先要sort
\(dp[i][j][2]\)表示解决了\(i,j\)这段区间，最后停留在\(i,j\)的答案
每次转移把周围每解决的点乘上时间作为贡献
const int N=1111,P=19650827;
template <typename T> void chk(T &a,T b){ if(a>b) a=b; }
int n,p;
ll a[N];
ll dp[N][N][2];
int main(){
n=rd(),p=rd();
rep(i,1,n) a[i]=rd();
sort(a+1,a+n+1);
memset(dp,10,sizeof dp);
rep(i,1,n) dp[i][i][0]=dp[i][i][1]=abs(a[i]-p)*n;
drep(i,n,1) rep(j,i,n) {
int t=n-(j-i+1);
if(i>1) {
chk(dp[i-1][j][0],dp[i][j][0]+abs(a[i]-a[i-1])*t);
chk(dp[i-1][j][0],dp[i][j][1]+abs(a[j]-a[i-1])*t);
}
if(j<n) {
chk(dp[i][j+1][1],dp[i][j][0]+abs(a[i]-a[j+1])*t);
chk(dp[i][j+1][1],dp[i][j][1]+abs(a[j]-a[j+1])*t);
}
}
printf("%lld\n",min(dp[1][n][0],dp[1][n][1]));
}
\[\
\]
\[\
\]
J [BZOJ1761] [Baltic2009]beetle
这题主体dp与上一题相同，但是这题并没有保证走所有点
但但是，这题保证每个点权值都一样大
直接枚举解决了几个点，然后转移
const int N=1111,P=19650827;
template <typename T> void chk(T &a,T b){ if(a>b) a=b; }
int n,m;
ll a[N];
ll dp[N][N][2];
int main(){
n=rd(),m=rd();
rep(i,1,n) a[i]=rd();
sort(a+1,a+n+1);
ll ans=0;
memset(dp,10,sizeof dp);
drep(len,n,1) {
if(1ll*len*m<=ans) break;
rep(i,1,n) dp[i][i][0]=dp[i][i][1]=len*abs(a[i]);
drep(i,n,1) {
rep(j,i,min(n,i+len-1)) {
ll t=len-(j-i+1);
if(i>1) {
chk(dp[i-1][j][0],dp[i][j][0]+t*abs(a[i]-a[i-1]));
chk(dp[i-1][j][0],dp[i][j][1]+t*abs(a[i-1]-a[j]));
}
if(j<n) {
chk(dp[i][j+1][1],dp[i][j][0]+t*abs(a[i]-a[j+1]));
chk(dp[i][j+1][1],dp[i][j][1]+t*abs(a[j]-a[j+1]));
}
if(j-i+1==len) ans=max(ans,1ll*(j-i+1)*m-min(dp[i][j][0],dp[i][j][1]));
dp[i][j][0]=dp[i][j][1]=1e18;
}
}
}
printf("%lld\n",ans);
}
\[\
\]
\[\
\]
K [BZOJ2037] [Sdoi2008]Sue的小球
同H,I
int n,p;
struct Node {
int x,y,v;
bool operator < (const Node __) const{
return x<__.x;
}
}A[N];
ll s[N];
ll dp[N][N][2];
int main() {
n=rd(),p=rd();
rep(i,1,n) A[i].x=rd();
rep(i,1,n) A[i].y=rd();
rep(i,1,n) A[i].v=rd();
sort(A+1,A+n+1);
ll sum=0;
rep(i,1,n) s[i]=s[i-1]+A[i].v,sum+=A[i].y;
memset(dp,10,sizeof dp);
rep(i,1,n) dp[i][i][0]=dp[i][i][1]=s[n]*abs(p-A[i].x);
drep(i,n,1) rep(j,i,n) {
ll t=s[n]-(s[j]-s[i-1]);
if(i>1) {
chk(dp[i-1][j][0],dp[i][j][0]+abs(A[i].x-A[i-1].x)*t);
chk(dp[i-1][j][0],dp[i][j][1]+abs(A[j].x-A[i-1].x)*t);
}
if(j<n) {
chk(dp[i][j+1][1],dp[i][j][0]+abs(A[j+1].x-A[i].x)*t);
chk(dp[i][j+1][1],dp[i][j][1]+abs(A[j+1].x-A[j].x)*t);
}
}
ll ans=sum-min(dp[1][n][0],dp[1][n][1]);
printf("%.3lf\n",ans/1000.0);
}
\[\
\]
\[\
\]
L [BZOJ2448]挖油
这个题复杂度可以写成\(O(n^2)\)的，但是由于我懒(菜)，写了个\(O(n^3 log n)\)的
题意：
有n个点，不知道每个点是0，1
并且连续有[0,x]是1，[x+1,n] 是0
要求x
有\(dp[i][i]=a[i]\),\(dp[i][j]=min(max(dp[i][k-1],dp[k+1][j])+a[k])\)
我们感性理解一下\(dp[i][j]\)随着\(j\)的增大或\(i\)的减小，值一定递增，所以二分\(dp[i][k-1],dp[k+1][j]\)的中间点\(mid\)
直接对于两边的\(dp[i][mid..j]+a[mid..j],dp[i..mid][j]+a[i..mid]\)取min即可
这两个范围最小值可以用某些数据结构维护
const int N=2019,P=19650827;
template <class T> void chk(T &a,T b){ if(a>b) a=b; }
int n;
int a[N],dp[N][N];
struct BIT{
int s[N];
void init(){
memset(s,10,sizeof s);
}
void Add(int p,int x) {
while(p) s[p]=min(s[p],x),p-=p&-p;
}
int Que(int p) {
int res=1e9;
while(p<=n) res=min(res,s[p]),p+=p&-p;
return res;
}
}A[N];
struct BIT2{
int s[N];
void init(){
memset(s,10,sizeof s);
}
void Add(int p,int x) {
while(p<=n) s[p]=min(s[p],x),p+=p&-p;
}
int Que(int p) {
int res=1e9;
while(p) res=min(res,s[p]),p-=p&-p;
return res;
}
}B[N];
int main(){
rep(i,1,n=rd()) a[i]=rd();
memset(dp,10,sizeof dp);
rep(i,1,n) dp[i][i]=a[i],dp[i+1][i]=dp[i][i-1]=0;
rep(i,1,n) {
A[i].init(),B[i].init();
A[i].Add(i,a[i]);
if(i<n) A[i].Add(i+1,a[i]+a[i+1]);
B[i].Add(i,a[i]);
if(i>1) B[i].Add(i-1,a[i]+a[i-1]);
}
drep(i,n,1) {
rep(j,i+1,n) {
int l=i,r=j,res=i-1;
while(l<=r) {
int mid=(l+r)>>1;
if(dp[i][mid-1]<=dp[mid+1][j]) l=mid+1,res=mid;
else r=mid-1;
}
dp[i][j]=min(dp[i][j],A[i].Que(res+1));
dp[i][j]=min(dp[i][j],B[j].Que(res));
if(dp[i][res-1]==dp[res+1][j]) dp[i][j]=min(dp[i][j],A[i].Que(res));
if(j<n) A[i].Add(j+1,dp[i][j]+a[j+1]);
if(i>1) B[j].Add(i-1,a[i-1]+dp[i][j]);
}
}
printf("%d\n",dp[1][n]);
}