HDU5697 刷题计划 dp+最小乘积生成树-白红宇

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

阅读量：4310 次

发布时间：2019-06-06

本文共 1505 字，大约阅读时间需要 5 分钟。

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

学习博客（必须先看这个）：

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 
      
       #include 
       
        using namespace std;const int N = 8e2+5;typedef long long LL;struct point{  int x, y;  point(int x=0,int y=0):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[0]=point(0,0),dp[0]=0;   for(int i=1;i<=sum;++i)dp[i]=1LL<<60;   for(int i=1;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+1;i<=sum;++i){     if(dp[i]
        
         
          =0)return;  solve(A,C);solve(C,B);}int main(){  while(~scanf("%d%d",&n,&m)){    sum=0;    for(int i=1;i<=n;++i){      scanf("%d%d%d",&a[i],&b[i],&c[i]);      sum+=a[i];    }    ans=1LL<<60;    for(int i=1;i<=n;++i)f[i]=b[i];    point A=get();    for(int i=1;i<=n;++i)f[i]=c[i];    point B=get();    solve(A,B);    printf("%I64d\n",ans);  }  return 0;}