记录编号	302880	评测结果	AAAAAAAAAA
题目名称	养猪	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2016-09-04 17:57:44	内存使用	3.77 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
#define	fcl	fclose(stdin);	fclose(stdout);	return 0
struct ss{
	int A,P;
}kito[1010];
int F[1010][1010]={0};
int n,k;

inline int Get_Max(int a,int b){
	return a>b?a:b;
}

bool Cmp(const ss& a,const ss& b){
	return a.P>b.P;
}

int main(){
	freopen("pig.in","r",stdin);
	freopen("pig.out","w",stdout);
	
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)	scanf("%d",&kito[i].A);
	for(int i=1;i<=n;++i)	scanf("%d",&kito[i].P);
	//如果k==n,显然所杀掉的猪初始总和是确定的，只需要保证损失掉的最小。
	//同理，如果说第a头猪和第j头猪都要杀，肯定先杀P值大的。
	//所以按照P大优先排序，按照普通背包做。第i头在第j天杀或不杀。 
	//这样就不用担心杀猪顺序了，因为所杀的猪一定是按照P降序杀的。 
	sort(kito+1,kito+1+n,Cmp);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=k;++j){
			F[i][j]=Get_Max(F[i-1][j],F[i-1][j-1]+Get_Max(kito[i].A-kito[i].P*(j-1),0));
			F[i][j]=Get_Max(F[i][j],F[i][j-1]);
		}
	}
	printf("%d",F[n][k]);
	fcl;
}
//end