题目链接： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3374

题意就是说有n棵树，每棵树有个初始值a个金币，而且每过一天会增加b个金币，求m天最多可以得到金币，而且必须每天都要砍一棵树

刚开始以为是贪心。。。Wa，后来举了个反例才发现自己的贪心是错的。。。那么应该怎么做这道题呢？？DP。。。除了贪心我只能想到DP，该怎么DP呢。。。后来想到来个数组dp[i][j]表示前i棵树在j天最大可以产生多少。。。但是有个特别的值。。就是b。。。好像又把我卡住了。。。想一下，就是怎么来确定顺序呢。。。根据b排序。。。把b最小的放前面。。。这样到后面的时候，b已经是最优的了。。。所以这道题的大致感觉就是。当前要放那个哪个地方的话。。。前面的得先放好而且是最优的

 ai[i][j]=max(ai[i-1][j],ai[i-1][j-1]+JLJ[i].b*(j-1)+JLJ[i].a);

这样答案就出来了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=250+10;
struct he
{
    int a,b;
} JLJ[maxn];
int ai[maxn][maxn];
int n,m;
int T;
bool cmp(he a,he b)
{
    return a.b<b.b;
}
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&JLJ[i].a);
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&JLJ[i].b);
    }
}
void play()
{   sort(JLJ+1,JLJ+1+n,cmp);
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {   if(j<=i)
            ai[i][j]=max(ai[i-1][j],ai[i-1][j-1]+JLJ[i].b*(j-1)+JLJ[i].a);
            else break;
        }
    }
    printf("%d\n",ai[n][m]);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}