P1070 道路游戏
斯德哥尔摩
2018-10-26 22:37:15
[P1070 道路游戏](https://www.luogu.org/problemnew/show/P1070)
这题还是很难的，至少我这么认为。
用一维数组$dp$储存第$i$秒能获得的最大钱数。
因为最多只能存在$1$个机器人，则若第$i$秒时第$j$个机器人走$k$次$(k\in[1,p])$。
那么状态转移方程长这样：
$$dp[i]=\max\{dp[i-k]-cost[last]+now\}$$
这里是从当前点倒推，$last$是上一个点。
当$last==0\text{或}last==n$时，$now$要一遍遍加上钱$k$秒第$last$路上的金币数。
每次减去第$last$条道路（即第$last$个工厂机器人）的价格。
如果$i-k<0$，直接退出$k$循环，因为时间不为负。
因为结果可能是负的，所以初始化为极小值。
一开始$dp[0]=0$，即第$0$秒金币数为$0$。
最后输出第$m$秒的值，即$dp[m]$。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 1010
using namespace std;
int n,m,q;
int money[MAXN][MAXN],cost[MAXN],dp[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
dp[0]=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
int t=j-1;
if(!t)t=n;
int now=money[t][i];
for(int k=1;k<=q;k++){
if(i<k)break;
dp[i]=max(dp[i],dp[i-k]+now-cost[t]);
t--;
if(!t)t=n;
now+=money[t][i-k];
}
}
printf("%d\n",dp[m]);
}
void init(){
n=read();m=read();q=read();
memset(dp,-127,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
money[i][j]=read();
for(int i=1;i<=n;i++)cost[i]=read();
}
int main(){
init();
work();
return 0;
}
```