Warm sunshine, cool wind and a fine day, while the girl watching is pursuing in chaos. Rikka reached out her hand and got the garland on her head, finding LCR with the immortal smile. The dream ended up waking, but the doubts will never disappear. In the end, without knowing about LCR, Rikka was invited to Shuyuan Men, a street of Chinese traditional arts in Xi’an.

        ”Is it enough to use the stored wires?”
        ”No problem… Those leaders are only concerned about expanding EC Final for the school’s and their ‘achievements’. All chores are ours. It is fine to simply connect those wiring boards in the series for each row.”
        Their conversation engaged Rikka. Feeling strange, she decided to follow them. But before all, she needs to beat the devil in her heart.
        Rikka has an aggressivity A and an increment D of it, which are both 0 initially. There are n rounds in total. For i=1,2,…,n, at the beginning of i-th round Rikka’s aggressivity A increases by the increment D, and then she can do one of the following:

  • Attack and cause a damage of (A+ai).
  • Use the Omnipotent Garland from LCR to increase the increment D by bi.
  • Use her Schwarz Sechs Prototype Mark II to increase the aggressivity A by ci.

        Rikka wonders the maximal possible damage she could cause in total. Could you help her?

Input

        The first line contains a single integer T (1≤T≤10), the number of test cases. Then T test cases follow.
        The input format of each test case is as follows:
        The first line contains a single integer n (1≤n≤100), the number of rounds.
        The following n lines contain {ai},{bi},{ci} for i=1,2,…,n. The i-th line among them contains three integers ai,bi,ci (1≤ai,bi,ci≤109) separated by spaces in order.
        It is guaranteed that the sum of n in all test cases is at most 100.

Output

        Output T lines; each line contains one integer, the answer to that test case.

题解

        比赛时遇到这题，充分体现了没智商、没脑子还不努力是一种什么体验。
        肯定是一个DP，但是状态压不动。正解是逆向DP。
        规定$dp(i)$为从$i$到$n$这些轮中最大的输出值，考虑前面的选择对后面的影响。由于操作二和操作三的存在，需要加上两维，变成$dp(i,j,k)$，它表示从$i$到$n$轮，一共输出了$j$次，选择输出的轮数下标为$k$的总最大输出值。
        那么状转方程：

        初始化$dp(i,0,0)=0$，其余负无穷大，跑一遍就完了。
        空间卡的比较紧，需要把第一维滚动掉。另外开long long。时间复杂度$O(n^4)$，空间复杂度$O(n^3)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

#define inf (1ll<<60)
using namespace std;
long long dp[2][105][5100];
int t, n, a[105], b[105], c[105], k;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)scanf("%d%d%d", a + i, b + i, c + i);
        k = 0;
        for (int j = 0; j <= n; j++) {
            for (int z = 0; z <= 5050; z++)dp[k][j][z] = -inf;
        }
        dp[k][1][n] = a[n], dp[k][0][0] = 0;
        for (int i = n - 1; i >= 1; i--) {
            k = !k;
            for (int j = 0; j <= n; j++) {
                for (int z = 0; z <= 5050; z++)dp[k][j][z] = -inf;
            }
            dp[k][0][0] = 0;
            for (int j = 0; j <= n; j++) {
                for (int z = 0; z <= 5050; z++) {
                    if (j >= 1 && z >= i)dp[k][j][z] = max(1ll * a[i] + dp[!k][j - 1][z - i], dp[k][j][z]);
                    dp[k][j][z] = max(dp[!k][j][z] + 1ll * (z - j * i) * b[i], dp[k][j][z]);
                    dp[k][j][z] = max(dp[!k][j][z] + 1ll * j * c[i], dp[k][j][z]);
                }
            }
        }
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 5050; j++)ans = max(ans, dp[k][i][j]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}