区间dp提升复习

区间\(dp\)提升复习

不得不说这波题真的不简单。。。

技巧总结：

1.有时候转移可以利用背包累和

2.如果遇到类似区间添加限制的题可以直接把限制扔在区间上，每次只考虑\([l,r]\)被\([i,j]\)完全包含的情况

[BZOJ4897] [Thu Summer Camp2016] 成绩单

典型的利用背包转移,\(dp[i][j]\)表示处理完这段\([i,j]\)区间的答案

转移时一段区间可以被先处理掉或者直接从已经处理完的\(dp[i][j]\)中取过来，这个可以用一个背包维护

const int N=52,P=999983,INF=1e9;

int n,a,b,w[N];
int dp[N][N];
int tmp[N][N][N];
int id[N*N];
inline void cmin(int &a,int b){ ((a>b)&&(a=b)); }
inline void cmax(int &a,int b){ ((a<b)&&(a=b)); }

int main(){
    n=rd(),a=rd(),b=rd();
    w[0]=0,w[n+1]=1001;
    rep(i,1,n) w[i]=rd();
    rep(i,0,n+1) id[w[i]]=i;
    memset(dp,63,sizeof dp);
    rep(i,1,n) {
        int ma=0,mi=INF;
        rep(j,i,n) {
            ma=max(ma,w[j]),mi=min(mi,w[j]);
            dp[i][j]=(ma-mi)*(ma-mi)*b+a;
        }
    }
    drep(i,n,1) {
        memset(tmp,63,sizeof tmp);
        tmp[i-1][n+1][0]=0;
        rep(j,i,n) {
            drep(k,j,i) {
                rep(a,0,n+1) {
                    rep(b,0,n+1) {
                        cmin(tmp[j][a][b],tmp[k-1][a][b]+dp[k][j]);
                    }
                }
            }
            rep(a,0,n+1) {
                rep(b,0,n+1) if(tmp[j-1][a][b]<INF) {
                    cmin(tmp[j][id[min(w[a],w[j])]][id[max(w[b],w[j])]],tmp[j-1][a][b]);
                }
            }
            rep(a,1,n) {
                rep(b,1,n) if(tmp[j][a][b]<INF) {
                    cmin(dp[i][j],tmp[j][a][b]+(::a)+::b*(w[b]-w[a])*(w[b]-w[a]));
                }
            }
        }
    }
    printf("%d\n",dp[1][n]);
}

\[\
\]

\[\
\]

[BZOJ4350] 括号序列再战猪猪侠

转移时考虑限制的\(dp\)

首先可以将这个问题转化为出入栈的问题，限制即出栈的先后

\(dp[i][j]\)即\(i\)到\(j\)这一段区间内的点都出栈的方案数

然后我们转移\(dp[i][j]\)时枚举最后一个出栈的\(k\)，检查是否符合限制即可 (简直不要太卡特兰数)

template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }

const int N=310,P=998244353;

int n,m;
ll dp[N][N];
int s[N][N];

int main(){
    rep(kase,1,rd()){
        n=rd(),m=rd();
        int fl=1;
        memset(s,0,sizeof s);
        rep(i,1,m) {
            int a=rd(),b=rd();
            if(a==b) fl=0;
            else s[b][a]++;
        }
        rep(i,1,n) rep(j,1,n) s[i][j]+=s[i][j-1];
        rep(i,1,n) rep(j,1,n) s[i][j]+=s[i-1][j];
        if(!fl) {
            puts("0");
            continue;
        }
        memset(dp,0,sizeof dp);
        rep(i,1,n+1) dp[i][i-1]=1;
        drep(i,n,1) {
            rep(j,i,n) {
                rep(k,i,j) {
                    int t=s[k-1][j]-s[i-1][j]-s[k-1][k-1]+s[i-1][k-1];
                    if(t) continue;
                    t=s[j][k]-s[k][k]-s[j][k-1]+s[k][k-1];
                    if(t) continue;
                    dp[i][j]=(dp[i][j]+dp[i][k-1]*dp[k+1][j])%P;
                }
            }
        }
        printf("%lld\n",dp[1][n]);
    }
}

\[\
\]

\[\
\]

[BZOJ4758] [Usaco2017 Jan]Subsequence Reversal

\(dp[i][j][a][b]\)表示\([i,j]\)这段区间\(LIS\)开始和结束为\(a,b\)的答案

然后向\(dp[i-1][j],dp[i][j+1]\)转移，考虑两边是否翻转即可

const int N=52,P=998244353;

int n;
int a[N];
int dp[N][N][N][N];

int main(){
    rep(i,1,n=rd()) a[i]=rd();
    rep(i,1,n) dp[i][i][a[i]][a[i]]=1;
    rep(i,1,n-1) dp[i][i+1][min(a[i],a[i+1])][max(a[i],a[i+1])]=2;
    drep(i,n,1) {
        rep(j,i,n) {
            if(i>1) {
                rep(a,1,50) rep(b,a,50) {
                    cmax(dp[i-1][j][a][b],dp[i][j][a][b]);
                    if(::a[i-1]<=a) cmax(dp[i-1][j][::a[i-1]][b],dp[i][j][a][b]+1);
                }
            }
            if(j<n) {
                rep(a,1,50) rep(b,a,50) {
                    cmax(dp[i][j+1][a][b],dp[i][j][a][b]);
                    if(::a[j+1]>=b) cmax(dp[i][j+1][a][::a[j+1]],dp[i][j][a][b]+1);
                }
            }
            if(i>1 && j<n) {
                rep(a,1,50) rep(b,a,50) {
                    cmax(dp[i-1][j+1][a][b],dp[i][j][a][b]);
                    if(::a[j+1]<=a) cmax(dp[i-1][j+1][::a[j+1]][b],dp[i][j][a][b]+1);
                    if(::a[i-1]>=b) cmax(dp[i-1][j+1][a][::a[i-1]],dp[i][j][a][b]+1);
                    if(::a[j+1]<=a && ::a[i-1]>=b) cmax(dp[i-1][j+1][::a[j+1]][::a[i-1]],dp[i][j][a][b]+2);
                }
            }
        }
    }
    int ans=0;
    rep(i,1,50) rep(j,1,50) cmax(ans,dp[1][n][i][j]);
    printf("%d\n",ans);
}

\[\
\]

\[\
\]

[BZOJ3379] [Usaco2004 Open] Turning in Homework 交作业

似乎是一道比较难的题

观察，其实我们可以认为一定是两边的房间先去，然后再去中间的

因为如果两边的房间还没有去完，那么以后走两边的房间时肯定也会路过中间的房间，那么也就没有必要先走中间的

如果这一点想到了，也就简单了吧

template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }

const int N=1010,P=998244353;

int n,m;
typedef pair<int,int> Pii;
Pii a[N];
int dp[N][N][2];

int main(){
    n=rd(),rd(),m=rd();
    rep(i,1,n) a[i].first=rd(),a[i].second=rd();
    sort(a+1,a+n+1);
    memset(dp,10,sizeof dp);
    dp[1][n][0]=max(a[1].second,a[1].first),dp[1][n][1]=max(a[n].second,a[n].first);
    rep(i,1,n) {
        drep(j,n,i) {
            if(i>1) {
                cmin(dp[i][j][0],dp[i-1][j][0]+abs(a[i].first-a[i-1].first));
                cmin(dp[i][j][1],dp[i-1][j][0]+abs(a[j].first-a[i-1].first));
            }
            if(j<n) {
                cmin(dp[i][j][0],dp[i][j+1][1]+abs(a[i].first-a[j+1].first));
                cmin(dp[i][j][1],dp[i][j+1][1]+abs(a[j].first-a[j+1].first));
            }
            cmax(dp[i][j][0],a[i].second);
            cmax(dp[i][j][1],a[j].second);
        }
    }
    int ans=1e9;
    rep(i,1,n) cmin(ans,min(dp[i][i][1],dp[i][i][0])+abs(a[i].first-m));
    printf("%d\n",ans);
}

\[\
\]

\[\
\]

[BZOJ3928] [Cerc2014] Outer space invaders

就是上文提到的区间加限制类型

每次从区间中取最大的一个限制出来，满足这个限制，也就是在这个限制区间里选择一个时间开枪

那么这段区间里所有跨过这个时间的点区间都会被打掉

没有跨过这个时间点的就直接加上

#include<cstdio>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

char IO;
int rd(){
    int s=0,f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

#define cmax(a,b) ((a<b)&&(a=b))
#define cmin(a,b) ((a>b)&&(a=b))

const int N=610;

int n;
int a[N],b[N],d[N];
int dp[N][N],ma[N][N];
int h[N],hc;

int main(){
    rep(kase,1,rd()) {
        hc=0;
        n=rd();
        rep(i,1,n) {
            a[i]=rd(),b[i]=rd(),d[i]=rd();
            h[++hc]=a[i];
            h[++hc]=b[i];
        }
        sort(h+1,h+hc+1),hc=unique(h+1,h+hc+1)-h-1;
        rep(i,1,hc) rep(j,i,hc) ma[i][j]=0,dp[i][j]=1e9;
        rep(i,1,n) {
            a[i]=lower_bound(h+1,h+hc+1,a[i])-h;
            b[i]=lower_bound(h+1,h+hc+1,b[i])-h;
            if(d[i]>d[ma[a[i]][b[i]]]) ma[a[i]][b[i]]=i;
        }
        rep(i,1,hc) rep(j,i+1,hc) {
            ((d[ma[i][j]]<d[ma[i][j-1]])&&(ma[i][j]=ma[i][j-1]));
            rep(k,i,j-1) ((d[ma[i][j]]<d[ma[k][j]])&&(ma[i][j]=ma[k][j]));
        }
        rep(i,1,hc) dp[i][i]=d[ma[i][i]];
        drep(i,hc,1) {
            rep(j,i,hc) {
                int id=::ma[i][j],ma=d[id];
                if(!id) dp[i][j]=0;
                else rep(k,a[id],b[id]) cmin(dp[i][j],dp[i][k-1]+dp[k+1][j]+ma);
            }
        }
        printf("%d\n",dp[1][hc]);
    }
}

\[\
\]

\[\
\]

POI2015 Washes

题目描述：

有n家洗车店从左往右排成一排，每家店都有一个正整数价格\(p[i]\)。

有\(m\)个人要来消费，第\(i\)个人会驶过第\(a[i]\)个开始一直到第\(b[i]\)个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于\(c[i]\)，那么这个人就不洗车了。

请给每家店指定一个价格，使得所有人花的钱的总和最大。

输入

第一行包含两个正整数\(n,m(1<=n<=50，1<=m<=4000)\)。

接下来m行，每行包含三个正整数\(a[i],b[i],c[i] (1<=a[i]<=b[i]<=n，1<=c[i]<=500000)\)

输出

第一行输出一个正整数，即消费总额的最大值。

第二行输出\(n\)个正整数，依次表示每家洗车店的价格\(p[i]\)，要求\(1<=p[i]<=500000\)。

若有多组最优解，输出任意一组。

解题报告

还是一道区间限制的题，依然定义 \(dp[i][j][k]\)表示考虑了所有\([l,r]\)被\([i,j]\)完全包含并且区间内最小值为\(k\)的答案

枚举最小值出现的位置和值，则两边的值要大于等于最小值，然后考虑所有跨过这个位置的区间的答案即可

#include<cstdio>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;

#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

char IO;
int rd(){
    int s=0,f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=52,M=4010;

int n,m;
vector <int> G[N][N];
int dp[N][N][M],f[N][N][M];
int h[M],hc;
int s[N][N][M],sum[N][N][M];
int to[N][N][M];

inline void chk(int &a,int b){ ((a<b)&&(a=b)); }

void Solve(int l,int r) {
    rep(i,l,r) {
        rep(j,1,hc) {
            int t=f[l][i-1][j]+f[i+1][r][j]+sum[l][r][j]-sum[l][i-1][j]-sum[i+1][r][j];
            if(t>dp[l][r][j]) dp[l][r][j]=t,to[l][r][j]=i;
        }
    }
    drep(j,hc,1) f[l][r][j]=max(dp[l][r][j],f[l][r][j+1]);
}

int res[N];

int dfs(int l,int r,int lim) {
    if(l>r) return 0;
    int ma=-1,id;
    rep(i,lim,hc) if(dp[l][r][i]>ma) ma=dp[l][r][i],id=i;
    res[to[l][r][id]]=id;
    dfs(l,to[l][r][id]-1,id);
    dfs(to[l][r][id]+1,r,id);
    return ma;
}

int main(){
    n=rd(),m=rd();
    rep(i,1,m) {
        int l=rd(),r=rd(),w=rd();
        h[++hc]=w;
        G[l][r].push_back(w);
    }
    sort(h+1,h+hc+1),hc=unique(h+1,h+hc+1)-h-1;
    rep(l,1,n) rep(r,l,n) rep(i,1,hc) rep(j,0,G[l][r].size()-1) s[l][r][i]+=((G[l][r][j]>=h[i])?h[i]:0);
    rep(k,1,hc) {
        rep(l,1,n) {
            rep(r,l,n) {
                sum[l][r][k]=sum[l][r-1][k];
                rep(i,l,r) sum[l][r][k]+=s[i][r][k];
            }
        }
    } // 预处理区间l,r内最小值为k的答案
    drep(i,n,1) {
        rep(j,i,n) {
            rep(k,1,hc) to[i][j][k]=i;
            Solve(i,j);
        }
    }
    printf("%d\n",dfs(1,n,1));
    rep(i,1,n) printf("%d ",h[res[i]]);
    puts("");
}

\[\
\]

\[\
\]

[BZOJ4856] [Jsoi2016] 病毒感染

我对题意的理解是：只要掉头了，就必须全部救完才能回来

所以我们考虑一段段区间地转移，每段区间内都是解决最远的点再回来解决最近的点

每一个区间\([l,r]\)的贡献都是可以直接预处理出来的

考虑区间\([l,r]\)内的每一个点，要么是第一次遇到就治，要么回来再治

两次的贡献分别是\(sum[r]-sum[i]\)(因为多停留了一天)，\(3*(r-i)*a[i]+a[i]\)(迟了这么多天)

（大概就是这么个意思，感性理解一下，可能是我说错了）

这个递推即可

template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }

const int N=3010;

int n;
ll a[N];
ll dp[N];
ll sum[N];
ll s[N][N];

int main(){
    n=rd();
    rep(i,1,n) a[i]=rd(),sum[i]=sum[i-1]+a[i];
    rep(i,1,n) {
        drep(j,i,1) {
            s[j][i]=s[j+1][i];
            s[j][i]+=sum[i]-sum[j];
            s[j][i]+=min(a[j]+(sum[i]-sum[j]),3*(i-j)*a[j]+a[j]);
        }
    }
    memset(dp,63,sizeof dp);
    ll ans=1e18;
    dp[0]=0;
    rep(i,1,n) {
        rep(j,1,i) {
            ll t=s[j][i]+(2*(i-j+1)+2*(i-j))*(sum[n]-sum[i]);
            cmin(dp[i],dp[j-1]+t);
            if(i==n) cmin(ans,dp[j-1]+s[j][i]+(2*(i-j+1)+(i-j))*(sum[n]-sum[i]));
        }
    }
    printf("%lld\n",ans-sum[n]);
}

\[\
\]

\[\
\]

[BZOJ3971] [WF2013]Матрёшка

理解题意过于痛苦

大概意思是说，合并成几段每段都是\([1..x]\)组成的

合并时的贡献其实是最小连续的一段都出现在\([i,k]\)或\([k+1,j]\)里的不用打开，其它都要打开的贡献

template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

const int N=510;

const char *Im="Impossible";

int n;
int dp[N][N],ans[N];
int a[N],cnt[N][N],c[N];
int mi[N][N],mk[N][N];

int main(){
    rep(i,1,n=rd()) {
        a[i]=rd();
        cnt[i][a[i]]++;
        if(a[i]>n) return puts(Im),0;
    }
    rep(i,1,n) rep(j,1,n) cnt[i][j]+=cnt[i][j-1];
    rep(i,1,n) rep(j,1,n) cnt[i][j]+=cnt[i-1][j];
    rep(i,1,n){
        memset(c,0,sizeof c);
        mk[i][i-1]=1;
        mi[i][i-1]=1e9;
        rep(j,i,n) {
            mk[i][j]=mk[i][j-1];
            if(++c[a[j]]>=2) mk[i][j]=0;
            mi[i][j]=min(mi[i][j-1],a[j]);
        }
    }
    memset(dp,63,sizeof dp);
    rep(i,1,n) dp[i][i]=0;
    drep(i,n,1) rep(j,i,n) if(mk[i][j]) {
        rep(k,i,j-1) {
            if(mi[i][k]<mi[k+1][j]) cmin(dp[i][j],dp[i][k]+dp[k+1][j]+(j-i+1)-(cnt[k][mi[k+1][j]]-cnt[i-1][mi[k+1][j]]));
            else cmin(dp[i][j],dp[i][k]+dp[k+1][j]+(j-i+1)-(cnt[j][mi[i][k]]-cnt[k][mi[i][k]]));
        }
    }
    memset(ans,63,sizeof ans);
    ans[0]=0;
    rep(i,1,n) drep(j,i,1) {
        if(cnt[i][i-j+1]-cnt[j-1][i-j+1]==i-j+1) {
            cmin(ans[i],ans[j-1]+dp[j][i]);
        }
    }
    if(ans[n]<1e8) printf("%d\n",ans[n]);
    else puts(Im);
}

\[\
\]

\[\
\]

[BZOJ4426] [Nwerc2015]Better Productivity最大生产率

把一堆区间分成\(k\)组，每组的交要\(>0\)，求交的总长的最大值

这里我们要把这些区间处理掉

首先，一个区间\([l,r]\)如果能够包含其他区间，那么对于它的决策就只有两种情况

1.和被某个他包含的区间放在一组，不影响这组的贡献

2.自己一个人开一组

把所有包含其他区间的提出来，剩下的区间一定都是满足\([l,r]\)递增的，这一部分我们用\(dp[i][j]\)计算前\(i\)个区间分成\(j\)组的答案

其他的区间，我们就是忽略，或者选择贡献最大的几个独自成一组

这样转移\(dp\)其实是明显的\(n^3\)，但是其实还可以优化，跑\(n \leq 1000\)的数据，留给各位神仙自己想吧

template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

const int N=210;

int n,m,c;
int dp[N][N];
int len[N],lc;
struct Node{
    int l,r;
    bool operator < (const Node __) const {
        return r<__.r||(r==__.r&&l>__.l);
    }
}A[N];

int main(){
    n=rd(),m=rd();
    rep(i,1,n) A[i].l=rd(),A[i].r=rd()-1;
    sort(A+1,A+n+1);
    int ma=-1;
    rep(i,1,n) {
        if(ma<A[i].l) ma=A[i].l,A[++c]=A[i];
        else len[++lc]=A[i].r-A[i].l+1;
    }
    n=c;
    memset(dp,-63,sizeof dp);
    dp[0][0]=0;
    rep(i,1,n) {
        rep(j,1,i) {
            drep(k,i,1) {
                if(A[i].l<=A[k].r) cmax(dp[i][j],dp[k-1][j-1]+A[k].r-A[i].l+1);
                else break;
            }
        }
    }
    int ans=0;
    sort(len+1,len+lc+1,greater<int>());
    rep(i,1,lc) len[i]+=len[i-1];
    rep(i,max(1,m-lc),min(m,n)) cmax(ans,dp[n][i]+len[m-i]);
    printf("%d\n",ans);
}