Miku

一道非常简单的dp，除非像我一样看错题

以为是所有猪全杀

然后写了个贪心，然后滚蛋

不过显然可以证明的是，优先取体重下降的快的猪，然后贪心

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,k;
struct pig{
    int a;
    int p;
}pi[10001];
bool cmp(pig x,pig y){
    if(x.p==y.p)
    return x.a>y.a;
    return x.p>y.p;
}
int ans;
int anss;
int dp[10001];
int main(){
    scanf("%d%d",&n,&k);
    for(long long i=1;i<=n;++i){
        scanf("%d",&pi[i].a);
    }
    for(long long j=1;j<=n;++j){
        scanf("%d",&pi[j].p);
    }
    sort(pi+1,pi+n+1,cmp);
    for(int z=1;z<=n;++z){
        for(int j=k;j>=1;--j){
            ans=max(0,pi[z].a-(j-1)*pi[z].p);
            dp[j]=max(dp[j],dp[j-1]+ans);
        }
    }
    ans=0;
    for(int i=1;i<=k;++i){
        ans=max(ans,dp[i]);
    }
    printf("%d",ans);
    return 0;
}