可以看出
第一天买,第三天卖 == 第一天买,第二天卖完再买,第三天卖
所以我们只考虑前一天买,后一天卖即可
那么有按天数来划分
f[i][j]表示前i天,共有j元,最大的盈利
第一维可以省去
那么有两种选择,不买 或者 前一天买,后一天卖
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 500001
#define max(x, y) ((x) > (y) ? (x) : (y)) int s, d, m;
int f[N], a[51][51]; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} int main()
{
int i, j, k;
s = read();
d = read();
m = read();
for(i = 1; i <= s; i++)
for(j = 1; j <= d; j++)
a[i][j] = read();
for(i = 2; i <= d; i++)
{
memset(f, 0, sizeof(f));
for(j = 1; j <= s; j++)
for(k = a[j][i - 1]; k <= m; k++)
f[k] = max(f[k], f[k - a[j][i - 1]] + a[j][i] - a[j][i - 1]);
m += f[m];
}
printf("%d\n", m);
}