Misunderstood … Missing

The first line contains a single integer $T~(1 \le T \le 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 \le n \le 100)$ , the number of rounds.
The following n lines contain $\{a_i\}, \{b_i\}, \{c_i\}$ for $i = 1, 2, \dots , n$ . The i-th line among them contains three integers $a_i, b_i, c_i~(1\le a_i, b_i, c_i \le 10^9)$ separated by spaces in order.
It is guaranteed that the sum of n in all test cases is at most 100.

C++11(clang++ 3.9) 解法, 执行用时: 75ms, 内存消耗: 9572K, 提交时间: 2020-03-17 13:40:21

#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=105;
int n,a[N],b[N],c[N];
long long f[N*N][N];
int main()
{
	int T;
	for(scanf("%d",&T);T--;)
	{
		scanf("%d",&n);
		int m=n*(n+1)/2;
		memset(f,-1,sizeof(f));
		for(int i=1;i<=n;++i) scanf("%d%d%d",&a[i],&b[i],&c[i]);
		f[n][1]=a[n];
		for(int i=n-1;i;--i)
		for(int j=m;j>=n;--j)
		for(int k=n-i+1;k;--k)
		{
			if(~f[j][k]) f[j][k]+=std::max(1LL*k*c[i],1LL*(j-i*k)*b[i]);
			if(j-i>=n&&k>=2&&~f[j-i][k-1]) f[j][k]=std::max(f[j][k],f[j-i][k-1]+a[i]);
		}
		long long ans=0;
		for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)
		ans=std::max(ans,f[i][j]);
		printf("%lld\n",ans);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 55ms, 内存消耗: 58872K, 提交时间: 2019-01-13 12:30:16

#include<bits/stdc++.h>
using namespace std;
long long dp[101][101][5001];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		for(int i=0;i<101;i++)
			for(int j=0;j<5001;j++)
				dp[0][i][j]=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			long long a,b,c;
			scanf("%lld%lld%lld",&a,&b,&c);
			for(int j=0;j<=n-i+1;j++)
			{
				for(int k=(1+j)*j/2;k<=(1+j)*j/2+(n-i+1-j)*j&&k<=5000;k++)
				{
					dp[i][j][k]=max(dp[i-1][j+1][k+j+1]+a,max(dp[i-1][j][k+j]+k*b,dp[i-1][j][k+j]+j*c));
				}
			}
		}
		printf("%lld\n",dp[n][0][0]);
	}
}

详情