//首先可以想到一个贪心，如果我们已经确定了要杀哪些猪，那么一定要先杀p比较大的
//这样我们可以p为第一关键字，a为第二关键字排序
//之后dp[i][j]表示前i头里杀了j头
//不断更新就可以了
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
    int a,p;
}q[1010];
int cmp(const node&x,const node&y)
{
    if(x.p!=y.p)
     return x.p>y.p;
    return x.a>y.a;
}
int dp[1010][1010];
int main()
{
    int n,i,j,k,ans=0;
    scanf("%d%d",&n,&k);
    if(k>n)
     k=n;
    for(i=1;i<=n;i++)
     scanf("%d",&q[i].a);
    for(i=1;i<=n;i++)
     scanf("%d",&q[i].p);
    sort(q+1,q+n+1,cmp);
    for(i=1;i<=n;i++)
     for(j=1;j<=k;j++)
      if(q[i].a-(j-1)*q[i].p>0)
       {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+q[i].a-(j-1)*q[i].p);
            ans=max(ans,dp[i][j]);
       }
    printf("%d",ans);
    return 0;
}

思路楼下williamchen大神
```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000 + 5;
const int INF = 1000000000;

struct Pig{
int a, b;
bool operator < (const Pig& rhs) const {
return b > rhs.b;
}
}p[maxn];

int n, K;
int d[maxn][maxn]; //d[i]:第i天杀垮价第j快的猪 i天内最大获益

void init(){
cin >> n >> K;
for (int i = 0; i < n; i++) scanf("%d", &p[i].a);
for (int i = 0; i < n; i++) scanf("%d", &p[i].b);
sort(p, p+n);
memset(d, -1, sizeof(d));
}

int dp (int i, int j) {
if (i > K||j >= n) return 0;
int& ans = d[i][j];
if (ans > -1) return ans;
int x = p[j].a - p[j].b*i;
if (x < 0) x = 0;
ans = max(dp(i+1, j+1) + x, dp(i, j+1));
return ans;
}

int main(){
freopen ( "in.txt" , "r" , stdin);
init();
cout << dp(0, 0);
return 0;
}
```

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

这题跟1574一样。一个程序刷两题。。

我从来没见过这么坑的题，害我WA了2次；DP倒是挺水，通过率这么低有以下几个原因
首先：题目里说是在K天以“内”啊，不一定要是K，但k越大不是更好吗，又不加负数的；至今仍跪求解释（我由10-100）；
其次：A[I]减的应该是p【i】*（j-1），我打成（i-1）了，手误（我由0-10）；
其次：题目里那个？其实是“价值》=0”，负数就算0！！！；
还有一些是在10-100期间徘徊的我，不断测样例发现错误的
1:应该要多关键快排，p相等时，A大还要排在前面，以下是自编样例：
3 3
14 12 13
9 7 7
不双排序，则是14+（12-7）+max（13-7*2,0）=19
而最优解是14+（13-7）+max（12-7*2,0）=20；
现在是给下水DP的思路：1.由题目可知p大的一定先杀，n=k时，显然因为都是总的价值-p【1】-p【2】*2-p【3】*3。。。可见前面越大总减得越小（即越优）。2.然后再思考，n比k大时，应该怎么办？因为a谁大并不知道，而杀的顺序一定是按照排玩序的来，无论k是多少；所以问题就变成在一些数中，任意选k个组成最优值（组合）；比如编号1,2,3,4,5有5个数，k=3时，可以1-2-3,1-2-4,3-4-5,2-4-5等5C3种组合中取最大的。
所以DP就特水：每个地方有2种情况，取与不取，即
f【i，j】:=max(f[i-1,j],f[i-1,j-1]+(a,p);
L.G.S-庆祝国庆节

对于N=K的情况我们发现，因为总和相同，只要按P[i]从大到小杀就可以了，这样损失最小
那么K>N时
选出的猪也一定满足P[I]从大到小，所以DP的顺序就出来了
先把P[i]排序
第K天杀或不杀第I头猪的最大收益
F[I,K]=max(f[I-1,K],F[I-1,K-1]+A[I,K])

把p[i]排序....再决绝k天后挂掉的猪...

略微有种果断贪心的感觉...

沙发

##怎么做啊！！！！##

这题目~~~略叼