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+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]<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=1;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)>=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;
}

?