Misunderstood … Missing【18EC】

Misunderstood … Missing

题意

初始攻击值 (A = 0) ,成长值 (D = 0) ， 每过一回合都会有 (A = A + D)

有 (n) 回合，每回合有三种选择

①. 造成 (A+a[i]) 的伤害

②. 提升 (b[i]) 的成长值

③. 提升 (c[i]) 的攻击值

给定 (n, a[],b[],c[])

求造成的最大伤害

由于二三操作对后面的影响是可以进行计算的

在设状态的时候可以只考虑一操作的状态从后往前 (dp)

设 f[pos][num][sum] 表示

从 (pos) 处开始到 (n) ，使用了 (num) 次操作 (1) , 并且这些位置的和是 (sum)

可以利用 (num) 和 (sum) 从后往前对二三操作直接计算贡献值

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll f[2][101][5055];

ll a[110], b[110], c[110];
ll T, n;
int main() {
	scanf("%lld", &T);
	while (T--) {
		scanf("%lld", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%lld%lld%lld", a + i, b + i, c + i);
		}
		memset(f, -0x3f, sizeof f);
		int now = 0;
		f[0][1][n] = a[n];
		f[0][0][0] = 0;
		for (ll i = n - 1ll; i >= 1; i--) {
			now ^= 1; int pre = now ^ 1;
			for (ll j = 0; j <= n - i; j++) {
				for (ll k = 0; k <= (n - i) * (n + i + 1) / 2; k++) {
					f[now][j + 1][k + i] = max(f[now][j + 1][k + i], f[pre][j][k] + a[i]);
					f[now][j][k] = max(f[now][j][k], f[pre][j][k] + (k - j * i) * b[i]);
					f[now][j][k] = max(f[now][j][k], f[pre][j][k] + c[i] * j);
				}
			}
		}
		ll ans = 0;
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= (n + 1) * n / 2; j++) {
				ans = max(ans, f[now][i][j]);
			}
		}
		printf("%lld
", ans);
	}
}