[ICPC2018西安I] Misunderstood … Missing

[ICPC2018西安I] Misunderstood … Missing - dp

Description

一共有n轮，你每次可以选择三种操作，第一种就是攻击怪兽,造成伤害A+ai，第二种就是提高自己的属性，以后每轮攻击力都增加bi，第三种提高攻击力，攻击力增加ci，问你最多能造成的伤害是多少。(n le 100)

Solution

设 (f[i][j][k]) 表示从第 (i) 轮到第 (n) 轮的过程中操作 (j) 次二类操作，而有 (k) 次实际的增量操作

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

#define int long long

int f[2][105][5005];

void solve()
{
    memset(f, 0, sizeof f);
    int n;
    cin >> n;
    vector<int> a(n + 2), b(n + 2), c(n + 2);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= n - i + 1; j++)
        {
            for (int k = j * (j + 1) / 2; k + j <= 5000; k++)
            {
                f[i & 1][j][k] = max(f[(i - 1) & 1][j + 1][k + j + 1] + a[i],
                                     max(f[(i - 1) & 1][j][k + j] + k * b[i], f[(i - 1) & 1][j][k + j] + j * c[i]));
            }
        }
    }
    cout << f[n & 1][0][0] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}