HDU5697 刷题计划 dp+最小乘积生成树

分析:就是不断递归寻找靠近边界的最优解

学习博客(必须先看这个):

1:http://www.cnblogs.com/autsky-jadek/p/3959446.html

2:http://blog.csdn.net/u013849646/article/details/51524748

注:这里用的最小乘积生成树的思想,和dp结合

每次找满足条件的最优的点,只不过BZOJ裸题的满足条件是形成一棵树

这个题是大于m,生成树借用最小生成树进行求解最优,大于m用dp进行求解最优

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 8e2+;
typedef long long LL;
struct point{
int x, y;
point(int x=,int y=):x(x),y(y){}
point operator -(const point &rhs)const{
return point(x-rhs.x,y-rhs.y);
}
point operator +(const point &rhs)const{
return point(x+rhs.x,y+rhs.y);
}
};
LL cross(point a,point b){
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
int n,m,sum;
int a[N],b[N],c[N];
point p[N];
LL dp[N],f[N],ans;
point get(){
p[]=point(,),dp[]=;
for(int i=;i<=sum;++i)dp[i]=1LL<<;
for(int i=;i<=n;++i){
for(int j=sum;j>=a[i];--j){
if(dp[j]>dp[j-a[i]]+f[i]){
dp[j]=dp[j-a[i]]+f[i];
p[j]=p[j-a[i]]+point(b[i],c[i]);
}
}
}
int ret=m;
LL tot=1LL*p[ret].x*p[ret].y;
for(int i=m+;i<=sum;++i){
if(dp[i]<dp[ret]||dp[i]==dp[ret]&&1ll*p[i].x*p[i].y<tot)
ret=i,tot=1ll*p[i].x*p[i].y;
}
ans=min(ans,tot);
return p[ret];
}
void solve(point A,point B){
for(int i=;i<=n;++i)
f[i]=1ll*c[i]*(B.x-A.x)+1ll*b[i]*(A.y-B.y);
point C=get();
if(cross(B-A,C-A)>=)return;
solve(A,C);solve(C,B);
}
int main(){
while(~scanf("%d%d",&n,&m)){
sum=;
for(int i=;i<=n;++i){
scanf("%d%d%d",&a[i],&b[i],&c[i]);
sum+=a[i];
}
ans=1LL<<;
for(int i=;i<=n;++i)f[i]=b[i];
point A=get();
for(int i=;i<=n;++i)f[i]=c[i];
point B=get();
solve(A,B);
printf("%I64d\n",ans);
}
return ;
}
上一篇:Zend Studio主题的设置


下一篇:Delphi中文件流的使用方法