Skip to content

线性dp/普通dp

坐标dp

P7074

由于从上往下有后效性，所以旋转90度后再做dp

对于每个坐标，都有两种方向，向左和向右。

所以设f[i][j][0/1]表示左/右方向时的最大值。

此时有转移方程：

\[ f[i][j][0]=max(f[i][j][0],max(f[i][j-1][0],f[i][j-1][1])+c[i][j]);(i=1\to n)\\ f[i][j][1]=max(f[i][j][1],max(f[i][j-1][0],f[i][j-1][1])+c[i][j]);(i=1\to n)\\ f[i][j][0]=max(f[i][j][0],f[i-1][j][0]+c[i][j]);(i=1\to n)\\ f[i][j][1]=max(f[i][j][1],f[i+1][j][1]+c[i][j]);(i=n\to 1) \]
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=1e3+10,INF=1e12;
int n,m;
int c[N][N],f[N][N][2];

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%lld",&c[i][j]);
        }
    }
    for(int i=0;i<=n+1;++i){
        for(int j=0;j<=m+1;++j){
            f[i][j][0]=-INF;
            f[i][j][1]=-INF;
        }
    }
    f[1][1][0]=f[1][1][1]=c[1][1];
    for(int j=1;j<=m;++j){
        for(int i=1;i<=n;++i){
            f[i][j][0]=max(f[i][j][0],max(f[i][j-1][0],f[i][j-1][1])+c[i][j]);
            f[i][j][1]=max(f[i][j][1],max(f[i][j-1][0],f[i][j-1][1])+c[i][j]);
            f[i][j][0]=max(f[i][j][0],f[i-1][j][0]+c[i][j]);
        }
        for(int i=n;i>=1;--i){
            f[i][j][1]=max(f[i][j][1],f[i+1][j][1]+c[i][j]);
        }
    }
    printf("%lld",max(f[n][m][0],f[n][m][1]));
    return 0;
}

P1437

因为从上往下搜会存在后效性，所以要从右往左搜。 设f[i][j][k]表示第i列去了j个砖块且总共去取了k个砖块的状态。

转移方程+code：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=55,M=N*N;
int n,m;
int a[N][N];
int f[N][N][M];
int t[N][N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n-i+1;++j){
            scanf("%d",&a[i][j]);
        }
    }
    memset(f,-0x3f,sizeof f); //避免不合法状态的转移。因为有v比k-j大的情况，这种情况不合法，因此应该为负无穷
    f[n+1][0][0]=0;//初始化
    int ans=0;
    for(int i=n;i>=1;--i){
        for(int j=0,sum=0;j<=n-i+1;++j,sum+=a[j][i]){
            for(int v=max(j-1,0)/*防溢出*/;v<=n-i;++v){//表示上一列至少要取j-1个，最多（n-i+1）-1个
                for(int k=j;k<=m;++k){
                    f[i][j][k]=max(f[i][j][k],f[i+1][v][k-j]+sum);
                }
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n-i+1;++j)ans=max(ans,f[i][j][m]);
    }
    printf("%d",ans);
    return 0;
} 
/*
4 6
2 2 3 4
8 2 7
2 3
49

*/

CF360B

~~我是傻逼~~

二分+dp

设dp[i]表示\(a_i\)不改时1~i最多不改的个数。

转移方程为：

    for(int i=2;i<=n;++i){
        for(int j=1;j<i;++j){
            if(x*(i-j)>=abs1(a[i]-a[j])){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }

条件是只要两个数相差在当前二分的长度范围内，那么就将i到j之间做更改，i和j保持不变，看最多留下几个数不改。

正确性是因为如果i到j之间有其他与i符合这个条件的数k，那么k一定会被i搜到，可能存在更优的结果。

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=2200,INF=0x7fffffff;
int a[N],dp[N];
int n,k;
int abs1(int x){
    return x>0?x:-x;
}
bool check(int x){
    int cnt=0;
    for(int i=1;i<=n;++i)dp[i]=1;
    for(int i=2;i<=n;++i){
        for(int j=1;j<i;++j){
            if(x*(i-j)>=abs1(a[i]-a[j])){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(i-dp[i]+n-i<=k)return true;
    }
    return false;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);

    int l=0,r=INF,ans=INF;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)){
            r=mid;
            ans=mid;
        }else l=mid+1;
    }
    printf("%lld",ans);


    return 0;
}

UVA1025

设\(f[i][j]\)表示在第\(j\)秒到达第\(i\)个车站时的最小等待时间。

那么每次由三种决策：

1) 如果不是1号车站并且此时有向左的车，就向左边。 2) 如果不是n号车站并且此时有向右的车，就向右边。 3) 在这个车站等待1秒。

判断此时有没有向左向右的车可以预处理出\(g[i][j][0/1]\)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=55,T=220,INF=0x3f3f3f3f;
int f[N][T],g[N][T][2];
int u[T],v[T],a[N],b[N],s[N];
int n,t,M1,M2,cnt;
void init() {
    memset(u,0,sizeof u);memset(v,0,sizeof v);memset(g,0,sizeof g);memset(f,0x3f,sizeof f);
    scanf("%d",&t);
    for(int i=1;i<n;++i)scanf("%d",&s[i]);
    a[1]=0;b[n]=0;
    for(int i=2;i<=n;++i)a[i]=a[i-1]+s[i-1];
    for(int i=n-1;i>=1;--i)b[i]=b[i+1]+s[i];
    scanf("%d",&M1);
    for(int i=1,tmp; i<=M1; ++i)scanf("%d",&tmp),u[tmp]=1;
    scanf("%d",&M2);
    for(int i=1,tmp; i<=M2; ++i)scanf("%d",&tmp),v[tmp]=1;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=t;++j)
            if(j>=a[i] && u[j-a[i]])g[i][j][1]=1;
            if(j>=b[i] && v[j-b[i]])g[i][j][0]=1;
    f[1][0]=0;
}
void dp(){
    for(int j=0;j<=t;++j)
        for(int i=1;i<=n;++i)
            if(g[i][j][0] && i>1)f[i-1][j+s[i-1]]=min(f[i-1][j+s[i-1]],f[i][j]);
            if(g[i][j][1] && i<n)f[i+1][j+s[i]]=min(f[i+1][j+s[i]],f[i][j]);
            f[i][j+1]=min(f[i][j+1],f[i][j]+1); 
}
int main() {
    while(1) {
        scanf("%d",&n);
        if(!n)return 0;
        ++cnt;
        init();
        dp();
        printf("Case Number %d: ",cnt);
        if(f[n][t]==INF)printf("impossible\n");
        else printf("%d\n",f[n][t]);
    }
    return 0;
}
  • 结论：将决策对应状态设成转移方程。

P5017

开始想到设\(f[i][j]\)表示有\(i\)个人等待，在第\(j\)分钟的情况。

~~后来发现直接爆炸~~

发现我们无法记录等待的人都是谁，所以就不记录，在转移时算出来。

所以设\(f[i][j]\)表示考虑到第\(i\)个人，第\(j\)分钟的情况，将\(f[i][j]\)转移到\(f[i+k][j+m]\)和\(f[i][j+1]\),表示立刻发车和等待一分钟的情况。

~~结果还是爆炸~~

正确做法是：

我们发现有个性质，就是每个人等待时间不超过\(m-1\)，因为就算这个人到达的前一秒钟发车，还是能在\(m-1\)秒后上车。

此时假设第\(i\)个人在\(t[i]+j\)秒上车，那么在\([t[i]+j+1,t[i]+j+m]\)秒内的人的等待时间就是这次转移的所有贡献，而不用加上\([t[i]+j-m+1,t[i]+j+m]\)秒内的贡献，因为这个在上一轮已经计算过了。

此时我们只考虑第\(i\)个人等待\(\min(m-1,t[i+1]-t[i])\)秒的时间即可。

设\(f[i][j]\)表示第\(i\)个人及之前的所有人要么已经到达了目的地，要么已经在车上时，且\(i\)恰好等了\(j\)秒才上车的最优解。

因为第\(i+1\)个人到第\(k\)个人都不会上车，都要等到\(t[i]+j+m=tmp+t[i+k]\)秒，所以他们等待的总时间为\(\sum_{v=i+1}^{i+k} tmp+t[i+k]-t[v]\),因为\(tmp+t[i+k]\)为定值，所以原式为$k* (tmp+t[i+k])-(s[i+k]-s[i]) $

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=550,INF=0x3f3f3f3f;
int f[N][N];
int t[N],s[N];
int n,m;
bool cmp(int a,int b){return a<b;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&t[i]);
    sort(t+1,t+n+1,cmp);
    for(int i=1;i<=n;++i)s[i]=s[i-1]+t[i];
    memset(f,0x3f,sizeof f);
    t[0]=-INF;
    f[0][0]=0;
    for(int i=0;i<=n;++i){
        int maxn=min(m-1,t[i+1]-t[i]);
        for(int j=0;j<=maxn;++j){
            if(f[i][j]>=INF)continue;

            for(int k=1;i+k<=n;++k){
                int tmp=max(t[i]+j+m-t[i+k],0);
                f[i+k][tmp]=min(f[i+k][tmp],f[i][j]+(tmp+t[i+k])*k-(s[i+k]-s[i]));
            }
        }
    }
    int ans=INF;
    for(int i=0;i<m;++i)ans=min(ans,f[n][i]);
    printf("%d",ans);
    return 0;
}

P3957

每次的\(dp\)就是取\([i-R,i-L]\)内的$f[j]_ { \max } $,而这个东西显然可以用单调队列维护。

注意每次的操作应该先从右加入元素，在从左删除，否则会出错~~这是个未解之谜？~~

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=5e5+10,INF=1e18;
int n,d,k;
int x[N],s[N],f[N];
int q[N];
bool check(int g) {
    int L=max(d-g,1ll),R=d+g,ans=-INF,l=1,r=0,tot=0;//注意出视状态的设定
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    memset(q,0,sizeof q);//存储的是最优解的标号1~n
    for(int i=1; i<=n; ++i) {
        while(x[tot]<=x[i]-L && tot<i) {//1,与2的顺序
            if(f[tot]>-INF) {//防止非法状态转移
                while(r>=l && f[tot]>f[q[r]])--r;
                q[++r]=tot;
            } 
            ++tot;
        }
        while(r>=l && x[i]-R>x[q[l]])++l;//2，被坑死，注意与1的顺序不要颠倒
        if(r>=l){
            f[i]=max(f[i],f[q[l]]+s[i]);
        }
        ans=max(ans,f[i]);  
    }
    return ans>=k;
}
signed main() {
    scanf("%lld%lld%lld",&n,&d,&k);
    for(int i=1; i<=n; ++i)scanf("%lld%lld",&x[i],&s[i]);
    int l=0,r=INF,ans=-1;
    while(l<r) {
        int mid=l+r>>1;
        if(check(mid)) {
            ans=mid;
            r=mid;
        } else l=mid+1;
    }
    if(l>=N) {
        printf("-1");
    } else printf("%lld",ans);
    return 0;
}
顺便练练双端队列\(deque\)来实现单调队列 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
const int N=5e5+10,INF=1e18;
int n,d,k;
int x[N],s[N],f[N];
int read1(){int x=0,f=1;char ch=getchar();while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch<='9' && ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
bool check(int g) {
    int L=max(d-g,1ll),R=d+g,ans=-INF,tot=0;
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    deque<int> q;
    for(int i=1; i<=n; ++i) {
        while(x[tot]<=x[i]-L && tot<i) {
            if(f[tot]>-INF) {
                while(!q.empty() && f[tot]>f[q.back()])q.pop_back();
                q.push_back(tot);
            } 
            ++tot;
        }
        while(!q.empty() && x[i]-R>x[q.front()])q.pop_front();
        if(!q.empty()){
            f[i]=max(f[i],f[q.front()]+s[i]);
        }
        ans=max(ans,f[i]);  
    }
    return ans>=k;
}
signed main() {
    n=read1(),d=read1(),k=read1();
    for(int i=1; i<=n; ++i)x[i]=read1(),s[i]=read1();
    int l=0,r=INF,ans=-1;
    while(l<r) {
        int mid=l+r>>1;
        if(check(mid)) {
            ans=mid;
            r=mid;
        } else l=mid+1;
    }
    if(l>=N) {
        printf("-1");
    } else printf("%lld",ans);
    return 0;
}
~~实测STL是真的慢，快读吸氧都拯救不了~~