P1070 道路游戏_牛客博客

观察下题目的状态，可设计出一个较为直接的方程。

对于 $f[t][cur][st]$ ， $t$ 代表当前时间， $cur$ 代表机器人即将走第几步，

$st$ 表示从第几个工厂出发。
则有:

$2<=t<=T,1<=cur<=p,1<=st<=n$

$cur=1$ 时，

$f[t][1][st]=max_{1<=cur<=p,1<=st<=n}{f[t-1][cur][st]}-hf[st]$

$2<=cur<=p$ 时, $f[t][cur][st]=f[t-1][cur-1][st-1]+v[t][st]$

（一开始写的时候把 $cur=1$ 时的方程写错了，丑）

边界就是 $f[1][1][st]=v[1][st]-hf[st]$

然后空间是不够的，易见第一维可以滚掉。

然后优化下 $max_{1<=cur<=p,1<=st<=n}{f[t-1][cur][st]}$ 就可以卡过此题。

#include<iostream>
#include<cstdio>
void read(int &s);
#define inf 1000000000
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int maxn=1010;
int maxx(int a,int b){return a<b?b:a;}

int n,m,p,hf[maxn],v[maxn][maxn],f[2][maxn][maxn];

int jian(int a){a--;return (a==0)?n:a;}
int main(){
    read(n);read(m);read(p);
    rep(i,1,n)
    rep(j,1,m)
    read(v[i][j]);
    rep(i,1,n)
    read(hf[i]);

    int mx0=-inf,mx=-inf,no=1;
    rep(st,1,n)f[0][1][st]=v[st][1]-hf[st],mx0=mx=maxx(mx,f[0][1][st]);
    rep(t,2,m){
        rep(st,1,n){
            f[no][1][st]=mx0+v[st][t]-hf[st],mx=maxx(mx,f[no][1][st]);
            for(int cur=2;cur<=p&&cur<=t;cur++)
            f[no][cur][st]=f[1-no][cur-1][jian(st)]+v[st][t],
            mx=maxx(mx,f[no][cur][st]);
        }
        mx0=mx;mx=-inf;
        no=1-no;
    }
    cout<<mx0;
    return 0;
}
void read(int &s){
    int k=1;s=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    s*=k;
}