题目链接：https://vijos.org/p/1574

这道题是昨晚一个叫Ztravellers的大佬推荐的，确实觉得这是一道很有意思的题，很多方面都很有意思；

初见这道题，估计想法都是贪心，因为各方面都很符合贪心，正解也用到了贪心，不过是在dp前贪心的；

 

思路：

我们砍树收集金币，肯定是希望损失最小，为了损失最小，肯定要尽量先砍每天损失最大的，从这个思想可以看出我们是需要排序的。但是也不一定就是一定要损失最大的，为了答案最优，我们还需要一个dp来做这个过程。定义一个d[i][j]表示前i棵树中砍j棵，当然这个形容还有很多，比如：第j天的时候判断第i棵树砍不砍；

然后因为金币是掉落，为了避免出错，所以在转移方程时要和0比一下大小

 

状态转移方程：d[i][i]=max{0,d[i-1][j],d[i-1][j-1]-per[i]*(j-1)};per数组是每棵树每天会损失的金币

题很简单，思路也不难想，打题也就是两次过，所以就直接出代码了

PS：有一个小小的问题还不是很清楚，昨晚询问了众多大佬都未果，所以在这里问问各位大佬，为啥答案不一定存在d[n][k]？？

上代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #define maxn 1005 9 using namespace std;10 11 struct node{12 int per,high;13 }e[maxn];14 15 int comp(const void*a,const void*b)16 {17 return (*(struct node*)a).per>(*(struct node*)b).per?-1:1;18 }19 20 int d[maxn][maxn],n,k,ans; 21 22 int main()23 {24 while(scanf("%d%d",&n,&k)!=EOF)25 {26 memset(d,0,sizeof(d));27 if(n==0&&k==0)return 0;28 for(int i=1;i<=n;i++)29 scanf("%d",&e[i].high);30 for(int i=1;i<=n;i++)31 scanf("%d",&e[i].per);32 e[0].per=0x3f3f3f;33 qsort(e,n+1,sizeof(e[0]),comp);34 int ans=0;35 for(int i=1;i<=n;i++)36 for(int j=1;j<=min(i,k);j++)37 {38 d[i][j]=max(0,max(d[i-1][j],d[i-1][j-1]+e[i].high-e[i].per*(j-1)));39 ans=max(ans,d[i][j]);40 } 41 // printf("%d\n",d[n][k]);42 printf("%d\n",ans);43 }44 45 46 }