二进制拆包

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<set>

#include<algorithm>

#include<map>

#include<vector>

#include<queue>

#include<iostream>

#include<string>

#define FOR(i,a,b) for(i=(a);i<=(b);i++)

#define ROF(i,a,b) for(i=(a);i>=(b);i--)

#define N 1000010

#define M 30010

typedef long long LL;

using namespace std;

int W[N],P[N];

int dp[M];

int main()

{

int n,T,i,m,t,p,j;

scanf("%d %d",&n,&T);

int len=0,sum=0;

FOR(i,1,n)

{

scanf("%d %d %d",&m,&t,&p);

sum+=m*p;

if (m*t>T) m=T/t;

for (j=1;j<=m;j<<=1) {m-=j;W[++len]=t*j,P[len]=p*j;}

if (m) W[++len]=t*m,P[len]=p*m;

}

FOR(i,1,len) ROF(j,T,W[i]) dp[j]=max(dp[j],dp[j-W[i]]+P[i]);

int ans=0;

FOR(i,0,T) if (dp[i]>ans) ans=dp[i];

printf("%d\n",sum-ans);

}

Views: 280 | Added by: dhy0077 | Rating: 5.0/1

Only registered users can add comments.
[ Sign Up | Login ]

Clever Space