http://acm.hdu.edu.cn/showproblem.php?pid=2670
 //1311986 2009-04-26 19:58:30 Accepted 2670 78MS 4180K 934 B C++ no way
#include<iostream>
#include<algorithm>
#define MAX(x,y) x>y?x:y
using namespace std;
struct node
   {
 int love;
int dece;
 };
bool comp(node a,node b)
{
return a.dece > b.dece;
}
int dp[1001][1001];//dp[i][j] 表示前i個(gè)人中選j個(gè)的最優(yōu)值
int lvs[1001][1001];
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
  {
int i,j,maxs;
node infor[1001];
for(i=1;i<=n;i++)
scanf("%d",&infor[i].love);
for(i=1;i<=n;i++)
scanf("%d",&infor[i].dece);
sort(infor+1,infor+n+1,comp);
/**/////////////////////////////////////////////////////////////////
for(i=1;i<=n;i++)
for(j=1;j<=k;j++)
lvs[i][j] = infor[i].love - (j-1)*infor[i].dece;
//這樣處理時(shí)間并未節(jié)約，相反還浪費(fèi)了空間~？？？？
/**/////////////////////////////////////////////////////////////////
maxs = 0;
for(i=1;i<=n;i++)
{
if(infor[i].love > maxs)
maxs = infor[i].love;
dp[i][1] = maxs;
 }
for(i=2;i<=n;i++)
{
for(j=2;j<=k && j<=i;j++)
{
if(i-1>=j)
dp[i][j] = MAX(dp[i-1][j],dp[i-1][j-1] + lvs[i][j]);
else
dp[i][j] = dp[i-1][j-1] + lvs[i][j];
}
}
cout<<dp[n][k]<<endl;
}
return 0;
}
|