斯德哥尔摩 的博客

斯德哥尔摩 的博客

P1070 道路游戏

posted on 2018-10-26 22:37:15 | under 刷题 |

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]$。

附代码:

#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;
}