洛谷 P1070 道路游戏

设为第i秒获得的最大值

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

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

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

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

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<cstring>

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

}