//比较正常的排序后DP
//首先贪心，如果已经确定要砍哪些树，那一定先砍b较大的
//于是把树进行排序，之后dp[i][j]表示前i棵树砍j棵
//DP就好了
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int m,b;
}q[1010];
int cmp(const node&x,const node&y)
{
    if(x.b!=y.b)
     return x.b>y.b;
    return x.m>y.m;
}
int dp[1010][1010];
int main()
{
    while(1)
    {
        int n,k,i,j,ans=0;
        scanf("%d%d",&n,&k);
        if(n==0&&k==0)
         break;
        for(i=1;i<=n;i++)
         scanf("%d",&q[i].m);
        for(i=1;i<=n;i++)
         scanf("%d",&q[i].b);
        sort(q+1,q+n+1,cmp);
        for(i=1;i<=n;i++)
         for(j=0;j<=min(i,k);j++)
           {
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
                if(j)
                 dp[i][j]=max(dp[i][j],dp[i-1][j-1]+q[i].m-q[i].b*(j-1));
                ans=max(ans,dp[i][j]);
           }
        printf("%d\n",ans);
        for(i=1;i<=n;i++)
         for(j=0;j<=k;j++)
          dp[i][j]=0;
    }
    return 0;
}

如果有对答案不存在F[n][k]里的同学，可以去讨论里交流下思路。

满足贪心选择性质!!!!

为什么这道题 dp[n][k]存的不是最佳答案呢 ?

#include<iostream>
#include<algorithm>
using namespace std;
struct GOLDTREE {int gold,lost;} gt[1010];
int n,k;
int dp[1010][1010];
bool cmp (GOLDTREE gt1,GOLDTREE gt2) {return gt1.lost>gt2.lost;}
void clear() {
    
    for(int i=1;i<=n;i++) gt[i].gold=gt[i].lost=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=k;j++)
        dp[i][j]=0;
    return;
    
} 
int main() {
    
    ios::sync_with_stdio(false);
    while(1) {
        cin>>n>>k;
        if (n==0&&k==0) break;
        for(int i=1;i<=n;i++) cin>>gt[i].gold;
        for(int i=1;i<=n;i++) cin>>gt[i].lost;  
        sort(gt+1,gt+n+1,cmp);
        int ans=0;
        for(int i=1;i<=n;i++) 
          for(int j=1;j<=k;j++)
            dp[i][j]=dp[i-1][j],dp[i][j]=max(dp[i][j],dp[i-1][j-1]+gt[i].gold-gt[i].lost*(j-1)),ans=max(ans,dp[i][j]);
        cout<<ans<<endl;
        clear();
    }
    return 0;   

}

为什么大家会讨论不砍的情况

谁能解释排序是为何？

楼下两个都是疯子

楼下乃抽神~

oh yeah~

Accepted 有效得分：100 有效耗时：0ms

___|\__|\__|\__|\__|_begin\___|\___|_

此题要选先排序 按掉钱的多少从大到小排序

因为对于一棵树来说 掉钱多 最好快点选

而选不选是DP的问题了

___|\__|\__|\__|\__|\__|\_^ ^\___|_

dp

a:=max{a,a+s1}

a为从前I棵数中选 j棵

s1为i在第J棵选 s1=m[i]-b[i]*(j-1); (★ S1有可能

令d表示前j天，第j天对i的处理，则

d=max{d,d+m[i]-b[i]*(j-1));

不砍i 砍i

注意：m[i]-b[i]*(j-1)会小于0 所以要判断一下和0的大小。

当然最重要的还是要先按照损失量排序一下。

因为要取最大，所以我们应该让损失降到最低。

至于这点voyagec2大牛已经为我们证明了。

Acceped

Accepted 有效得分：100 有效耗时：0ms

Accepted 有效得分：100 有效耗时：0ms

首先要先排序，才能无后效

a[q,j]:=a[p,j]; if a[p,j-1]+max(0,b[i]-(j-1)*d[i])>a[q,j] then a[q,j]:=a[p,j-1]+max(0,b[i]-(j-1)*d[i]); if a[q,j]>ans then ans:=a[q,j];

楼上的不要无聊了

首先，如果没有k天的限制，很明显的贪心。

而当有了k天的限制,问题不一样了，不过，我们很清楚，最尤解

砍树的顺序肯定按树的递减量的。（这里我就不证明了，自己想想）

这样，dp就表示第i天砍最后一棵树的最优解.

贪心 每天将会掉落的金币+dp

既可过

最后要再找最优（因没找我wa多次）

一次AC，秒杀！！！

排序是关键。

如果想到了，那DP就不难想出来了。

ls的大牛们讲得很详细了，这里就不哆嗦了。

按损失值排序，为什么？，我们要求的是能够得到的最多金币，所以应该把所有的损失值降到最低，怎么做，就是一定的天数内，若树的范围确定了，那么先把损失值最大的依次砍下就一定能达到最优解！

注意：每天可以砍掉其中一颗，也可以不砍

请问为什么F也要从F赋值？

F不是应该>=F的吗？

可是没加这句我就20

加了就AC了。。为什么啊

请教各位！！

过了，但是为什么要按每天丢的排序？

谁能给个证明？