HDU 5534 完全背包

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2020;
int f[MAXN];
int d[MAXN];



int main()
{
    //freopen("in.txt","r",stdin);
    int T_T;
    scanf("%d",&T_T);
    while(T_T--) {
        int n;
        scanf("%d",&n);

        for(int i = 1; i <= n-1; i++) scanf("%d",&f[i]);

        memset(d,-1e9-7,sizeof(d));

        d[0] = n*f[1];

        for(int i = 1; i <= n-2; i++) {
            for(int j = 0; j <= n-2; j++) {
                if(j>=i)
                    d[j] = max(d[j],d[j-i]+f[i+1]-f[1]);
            }
        }

        cout<<d[n-2]<<endl;

    }

    return 0;
}