hdoj2670

12004 단어 OJ
Problem : 2670 ( Girl Love Value )     Judge Status : Accepted RunId : 2682427    Language : G++    Author : huwenbiao Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
/***************************************************************\
*Author:Hu Wenbiao
*Created Time: Sun 25 Jul 2010 04:32:08 PM CST
*File Name: main.cpp
*Description: 。 , boy
* , boy
* , ,
*boy, , ,
* 。dp[i][j] i boy j
\***************************************************************/

//*========================*Head File*========================*\\

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
/*----------------------*Global Variable*----------------------*/
int
dp[
1010][1010],n,K;
struct
Boy{
int
l,b;
}
boy[
1010];
//*=======================*Main Program*=======================*//
using namespace std;

bool
cmp(Boy a,Boy b){
return
a.b>b.b;
}


int
main(){

//freopen("input","r",stdin);
while(scanf("%d%d",&n,&K)!=EOF){
for
(int i=
1;i<=n;i++)
scanf(
"%d",&boy[i].l);
for
(int i=
1;i<=n;i++)
scanf(
"%d",&boy[i].b);
sort(boy+
1,boy+1+n,cmp);
// memset(dp,0,sizeof(dp));
dp[1][1]=boy[1].l;
for
(int i=
2;i<=n;i++)
for
(int j=
1;j<=i;j++)
if
(i==j)
dp[i][j]=dp[i-
1][j-1]+boy[i].l-(j-1)*boy[i].b;
else

dp[i][j]=max(dp[i-
1][j],dp[i-1][j-1]+boy[i].l-(j-1)*boy[i].b);
printf(
"%d
"
,dp[n][K]);
}
}

좋은 웹페이지 즐겨찾기