非常好的一个题，第一眼看到就觉得是贪心或者DP。
首先，一开始的思路是枚举第k天，然后把第k天最大的放入，但是保证每天放入剩下的树中对于这一天最大的，不一定是最优方案，所以不能枚举了。
正解：dp，dp[i][j]表示到第i棵树，天数为j的最大代价。
转移很简单，但是这里直接去dp，还不太对，因为有些树可能应该在后面砍，但是它前面的树太少导致中间代价有空，导致不被算入最大代价中。
所以需要按b[i]来排序。把增长的慢的先砍，并且这样是不会受到a[i]的影响的。
可以理解一下，我们是在对树dp，所以本质上砍的那些树都是按天数排列，所以增长慢的先砍肯定更优。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,int> pii; const int N = 1005; const int M = 1e6+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < ‘0‘ || c > ‘9‘){if(c == ‘-‘) f = -1;c = getchar();} while(c >= ‘0‘ && c <= ‘9‘){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar(‘-‘);} if(x > 9) print(x/10); putchar(x%10+‘0‘); } } using namespace FASTIO; struct Node{int a,b;}p[255]; int n,m,dp[255][255];//dp[i][j] - 到第i棵树第j天的最大价值 bool cmp(Node a,Node b){return a.b < b.b;} int main() { int ca;ca = read(); while(ca--) { n = read(),m = read(); for(rg int i = 1;i <= n;++i) p[i].a = read(); for(rg int i = 1;i <= n;++i) p[i].b = read(); sort(p+1,p+n+1,cmp); memset(dp,0,sizeof(dp)); for(rg int i = 1;i <= n;++i) { for(rg int j = 1;j <= m;++j) { dp[i][j] = max(dp[i-1][j-1] + p[i].a + (j-1)*p[i].b,dp[i-1][j]); } } printf("%d\n",dp[n][m]); } system("pause"); return 0; }
原文：https://www.cnblogs.com/zwjzwj/p/13769338.html
