P2065 贪心的果农

题目描述

果农的花园里种着N棵果树。收获的季节终于来到了，果农决定，在接下来的M天时间里完成自己的收获工作。他的收获方式极其暴力——他将会将某棵果树砍倒来获取上面的果实。然而如此暴力的果农体力也十分有限，他每天最多只能砍一棵果树。已经知道，对于第i棵果树，在第1天的时候上面已经有ai个果实，而接下来每一天（不包括第1天），它都会再长出bi个果实(0<=ai,bi<=104，ai,bi均为整数)。果农只能获得砍下来的果树上的果实，而砍下来的果树将不会再长果实。果农想知道，自己在M天后最多可以收获多少个果实。

输入输出格式

输入格式：

第1行包含两个整数N，M。

第2行N个数，用空格隔开，第i个数表示ai。

第3行N个数，用空格隔开，第i个数表示bi。

输出格式：

一个数，表示最多能获得到的果实。

输入输出样例

输入样例#1：

2 2
8 10
2 3

输出样例#1：

说明

数据规模

对于30%的数据，0<M,N<=30；

对于100%的数据，0<M,N<=1000；

数据保证答案小于等于231-1。

分析

dp[i]到第i天的最大收获，如果我们外层循环天数，内层枚举树，取最大值，那么上一天的最大值，可能已经用了第x棵树，当前在枚举x是不合理的，所以要外层循环树，内层循环天，表示这棵树在第几天砍掉。状态转移方程：

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

code

 1 #include<algorithm>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 struct MYSTRUCT{
 6     int a,b;
 7     bool operator < (const MYSTRUCT& c) const 
 8     {
 9         if (b==c.b) return a < c.a;
10         return b < c.b;
11     }
12 }f[1010];
13 int dp[1010];
14 
15 int main()
16 {
17     int n,m;
18     scanf("%d%d",&n,&m);
19     for (int i=1; i<=n; ++i) scanf("%d",&f[i].a);
20     for (int i=1; i<=n; ++i) scanf("%d",&f[i].b);
21     sort(f+1,f+n+1);
22     for (int i=1; i<=n; ++i)
23         for (int j=m; j>=1; --j)
24             dp[j] = max(dp[j],dp[j-1]+f[i].a+f[i].b*(j-1));
25     printf("%d",dp[m]);
26     return 0;
27 }