zoj3956_Solution
H=sum(hi),C=sum(ci),Value=H*H-H*C-C*C
求Value的最大值
Solution：
动态规划：
共两维：H,C 固定一维C，在该维值C相同的情况下另一维应最大H，从而动态规划另一维H，转变为01背包问题。
优化：
H*H-H*C-C*C=0 (H,C>0)
H/C=(1+sqrt(5))/2=1.6180…
必会选择h/c>(1+sqrt(5))/2 的(h,c)对
证明：
若Value大于0，则H/C>(1+sqrt(5))/2，
若再加上h/c>(1+sqrt(5))/2 的(h,c)对，
(H+h)* (H+h)-(H+h) *(C+c)-(C+c)* (C+c)=H*H-H*C-C*C+h*h-h*c-c*c+2*H*h-H*c-h*C-2*C*c
[ (H+h)* (H+h)-(H+h) *(C+c)-(C+c)* (C+c) ] – [ H*H-H*C-C*C ]
= h*h-h*c-c*c+2*H*h-H*c-h*C-2*C*c
>2*H*h-H*c-h*C-2*C*c
>2*H*h - H*h*(1+sqrt(5))/2 - h*H*(1+sqrt(5))/2 – 2*H*(1+sqrt(5))/2*h*(1+sqrt(5))/2
=0
值必然会增大，所以必会选择h/c>(1+sqrt(5))/2 的(h,c)对，得证
所以可以把h/c>=(1+sqrt(5))/2的(h,c)对先选出来，再对h/c<(1+sqrt(5))/2的(h,c)对进行动态规划，然后在动态规划的基础上再加上h/c>=(1+sqrt(5))/2的(h,c)对求得在相同C的基础上H的最大值。
某个贪心的方法：按照h/c从大到小的顺序依次对h,c对进行排序，然后依次选取，直到值小于0。
证明不成立：
原来 H,C value
加入 h1,c1 value1
再加入 h2,c2 value2
（h1/c1>h2/c2）
若原来加入 h2,c2 value3
证明有可能只加入h2,c2数值更大：
h1,c1数值非常大，且h1/c1<(1+sqrt(5))/2，加入h1,c1后value1<0，而再加入h2,c2后，value2<value1<0；而尽管h2/c2< h1/c1<(1+sqrt(5))/2，但加入h2,h2后，value2>value。
如H=1700,C=1000
h1=16000,c1=10000
h2=159,c1=100
value=190000
value1=-2410000
value2=-2501019
value3=200981
当有三个数据(1700,1000),(16000,10000),(159,100)，则用此方法求得结果为190000，并不正确。所以该方法错误。
DP：
#include <stdio.h>
#include <stdlib.h>
#define maxn 500 int main()
{
//500*100(total) *500(n) *10(test cases)=250000000 //max_result=(10000*500)^2
//the maximum of h[i] is larger than c[i],thus choose c
//the total of c is not larger than 500*100=50000
//when c is the same , we need maximum h
long h[maxn+],c[maxn+];
//<=10000/100*500
long t,n,i,j,k,ans[maxn+],f[];
long long s,result;
scanf("%ld",&t);
for (k=;k<=t;k++)
{
ans[]=;
result=;
scanf("%ld",&n);
for (i=;i<=n;i++)
{
scanf("%ld %ld",&h[i],&c[i]);
ans[i]=ans[i-]+c[i];
}
for (i=;i<=ans[n];i++)
f[i]=-;
f[]=;
for (i=;i<=n;i++)
//when choose course ith ,the maximum of credit is ans[i](including c[i])
for (j=ans[i];j>=c[i];j--)
if (f[j-c[i]]!=- && f[j-c[i]]+h[i]>f[j])
f[j]=f[j-c[i]]+h[i];
for (i=;i<=ans[n];i++)
if (f[i]!=-)
{
s=f[i]*f[i]-f[i]*i-i*i;
if (s>result)
result=s;
}
printf("%lld\n",result);
}
return ;
}
/*
100 1 1 1 1 1 1 1 1
0+101+102+……
not obvious WorstSituation
10 10 10 10 10
50+50+50+50+50=250
0+10+20+30+40=100
save halt of the time Previous:
49900*500=24950000
Current:
0+100+200+…+49900=12500000
10Cases
12500000*10=1,2500,0000
*/
DP(advance)：
#include <stdio.h>
#include <stdlib.h>
#define maxn 500 //原来60s，现在20s int main()
{
//500*100(total) *500(n) *10(test cases)=250000000 //max_result=(10000*500)^2
//the maximum of h[i] is larger than c[i],thus choose c
//the total of c is not larger than 500*100=50000
//when c is the same , we need maximum h
long h[maxn+],c[maxn+],ans[maxn+],f[];
//<=10000/100*500
long t,n,i,j,k,g,temp,hh,cc;
long long s,result;
double line=(1.0+sqrt(5.0))/;
scanf("%ld",&t);
for (k=;k<=t;k++)
{
ans[]=;
scanf("%ld",&n);
for (i=;i<=n;i++)
scanf("%ld %ld",&h[i],&c[i]);
g=n+;
for (i=n;i>=;i--)
if (1.0*h[i]/c[i]>=line)
{
g--;
temp=h[i];
h[i]=h[g];
h[g]=temp;
temp=c[i];
c[i]=c[g];
c[g]=temp;
}
g--;
//a[g+1]~a[n] h[i]/c[i]>=line must be chose
hh=;
cc=;
for (i=g+;i<=n;i++)
{
hh+=h[i];
cc+=c[i];
}
//a[1]~a[g] h[i]/c[i]<line
for (i=;i<=g;i++)
ans[i]=ans[i-]+c[i];
for (i=;i<=ans[g];i++)
f[i]=-;
f[]=;
for (i=;i<=g;i++)
//when choose course ith ,the maximum of credit is ans[i](including c[i])
for (j=ans[i];j>=c[i];j--)
if (f[j-c[i]]!=- && f[j-c[i]]+h[i]>f[j])
f[j]=f[j-c[i]]+h[i];
result=hh*hh-hh*cc-cc*cc;
for (i=;i<=ans[g];i++)
if (f[i]!=-)
{
s=(f[i]+hh)*(f[i]+hh)-(f[i]+hh)*(i+cc)-(i+cc)*(i+cc);
if (s>result)
result=s;
}
printf("%lld\n",result);
}
return ;
}
/*
100 1 1 1 1 1 1 1 1
0+101+102+……
not obvious WorstSituation
10 10 10 10 10
50+50+50+50+50=250
0+10+20+30+40=100
save halt of the time Previous:
49900*500=24950000
Current:
0+100+200+…+49900=12500000
10Cases
12500000*10=1,2500,0000
*/
贪心(Wrong):
#include <stdio.h>
#include <stdlib.h>
#define maxn 500 struct node
{
long h,c;
double per;
}; int cmp(const void *a,const void *b)
{
if ((*(struct node *)b).per>(*(struct node *)a).per)
return ;
else
return ;
} long long max(long long a,long long b)
{
if (a>b)
return a;
else
return b;
} int main()
{
long t,k,l,n,ht,ct;
long long maxs;
struct node course[maxn+];
scanf("%ld",&t);
for (k=;k<=t;k++)
{
scanf("%ld",&n);
for (l=;l<n;l++)
{
scanf("%ld%ld",&course[l].h,&course[l].c);
course[l].per=1.0*course[l].h/course[l].c;
}
qsort(course,n,sizeof(struct node),cmp);
ht=;
ct=;
maxs=;
for (l=;l<n;l++)
{
ht+=course[l].h;
ct+=course[l].c;
maxs=max(maxs,ht*ht-ht*ct-ct*ct);
}
printf("%lld\n",maxs);
}
return ;
}
/*
5
1 4
2 5
6 3
7 2
4 4
*/
最普通的方法，保证正确，用于测试其它程序是否正确：
#include <stdio.h>
#include <stdlib.h> struct node
{
long h,c;
double per;
};
long n;
long long maxs=;
struct node course[]; int cmp(const void *a,const void *b)
{
return (*(struct node *)b).per-(*(struct node *)a).per;
} long long max(long long a,long long b)
{
if (a>b)
return a;
else
return b;
} void dfs(long d,long ht,long ct)
{
if (d==n)
return ;
if (ct!=)
maxs=max(maxs,ht*ht-ht*ct-ct*ct);
dfs(d+,ht+course[d].h,ct+course[d].c);
dfs(d+,ht,ct);
} int main()
{
long t,k,l;
scanf("%ld",&t);
for (k=;k<=t;k++)
{
scanf("%ld",&n);
maxs=;
for (l=;l<n;l++)
{
scanf("%ld%ld",&course[l].h,&course[l].c);
course[l].per=1.0*course[l].h/course[l].c;
}
dfs(,,);
printf("%lld\n",maxs);
}
return ;
}
以下是我做的关于此题做的评测方法，值得一览
http://pan.baidu.com/s/1c1WeUGS
