#include <iostream>
#include <cstdio>
#include <cstring>
#define N 500
#define M 850
using namespace std;
struct point{int x,y;point(const int &A,const int &B){x=A;y=B;}point(){}};
typedef point Vector;
Vector operator - (const point &a,const point &b){return Vector(a.x-b.x,a.y-b.y);}
inline long long Cross(Vector A,Vector B){return 1LL*A.x*B.y-1LL*A.y*B.x;}
int n,m,x[N],y[N],v[N],top;
long long F[M],ans;
long long rk[M]; //記錄本次DP第i個題目的優先級
point rc[M]; //記錄到達獲得i收益的點(x,y)
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
point DP()
{
point now;
now.x = now.y = 4000000;
for (int i=1;i<=top;i++) F[i] = 1LL << 62;
F[0] = 0LL;
for (int i=1;i<=n;i++)
for (int j=top;j>=v[i];j--)
if (F[j] > F[j-v[i]] + rk[i]) {
rc[j].x = rc[ j-v[i] ].x + x[i];
rc[j].y = rc[ j-v[i] ].y + y[i];
F[j] = F[j-v[i]] + rk[i];
}
int k = m;
for (int i=m;i<=top;i++) if (F[k] > F[i]) k = i;
now = rc[k];
ans = min(ans,1LL*now.x*now.y);
return now;
}
void solve(point A,point B)
{
for (int i=1;i<=n;i++) rk[i] = 1LL * x[i] * (A.y - B.y) + y[i] * (B.x - A.x); //更新關鍵詞
point C = DP();
if(Cross(B-A,C-A)>=0) return ; //尋找不到直線AB左下方的點
solve(A,C);solve(C,B); //分成兩部分遞回
}
int main()
{
ans = 1LL << 62;
while (~scanf("%d%d",&n,&m))
{
for (int i=1;i<=n;i++) {v[i] = read();x[i] = read(); y[i] = read();}
for (int i=1;i<=n;i++) top += v[i];
for (int i=1;i<=n;i++) rk[i] = 1LL*x[i]; //DP關鍵詞為橫坐標
point A = DP(); //尋找最靠近y軸的點
for (int i=1;i<=n;i++) rk[i] = 1LL*y[i]; //DP關鍵詞為縱坐標
point B = DP(); //尋找最靠近x軸的點
solve(A,B); //遞回尋找在A,B左下方的點
printf("%I64d\n",ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/282045.html
標籤：Java相關
上一篇：java多執行緒編程
下一篇：Mybatis使用注解開發