[ICPC2018西安I] Misunderstood … Missing - dp

[ICPC2018西安I] Misunderstood … Missing - dp

Description

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

Solution

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

#include 
using namespace std;

#define int long long

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

void solve()
{
    memset(f, 0, sizeof f);
    int n;
    cin >> n;
    vector 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();
    }
}