洛谷 P1070 道路游戏-白红宇

洛谷 P1070 道路游戏

阅读量：6332 次

发布时间：2019-06-22

本文共 1065 字，大约阅读时间需要 3 分钟。

设 $f[i]$ 为第i秒获得的最大值

$f[j] = max(f[j-k] + sum - cost[pos])$

表示从当前世界是j，从pos走k步到当前点i的最大价值

注意这里的sum可以利用前面的值逐步累加。

我开始做的时候没有想到这一点单独求，然后就超时了。

同时要注意循环的循序问题。

#include
    
     #include
     
      #include
      
       #include
       
        #define REP(i, a, b) for(int i = (a); i < (b); i++)#define _for(i, a, b) for(int i = (a); i <= (b); i++)using namespace std;const int MAXN = 1123;int f[MAXN], money[MAXN][MAXN];int cost[MAXN], n, m, p;void read(int& x){	int f = 1; x = 0; char ch = getchar();	while(!isdigit(ch)) { if(ch == '-1') f = -1; ch = getchar(); }	while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }	x *= f;}int main(){	read(n); read(m); read(p); 	REP(i, 0, n)		_for(j, 1, m)			read(money[i][j]);	REP(i, 0, n) read(cost[i]);		memset(f, 0xc0, sizeof(f));	f[0] = 0;		_for(j, 1, m)		REP(i, 0, n)		{			int pos = (i - 1 + n) % n;			int sum = money[pos][j];			_for(k, 1, min(j, p))			{				f[j] = max(f[j], f[j-k] + sum - cost[pos]);				pos = (pos - 1 + n) % n;				sum += money[pos][j-k];			}		}	printf("%d\n", f[m]);		return 0;}