http://poj.org/problem?id=2754
先把low--up 转化为0--(up-low)
然后变成背包 背包的关键在于多重背包用二进制优化
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<map> #include<vector> #include<stack> #include<set> #include<map> #include<queue> #include<algorithm> #include<cmath> #define LL long long //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const int INF=0x3f3f3f3f; const int N=205; const int M=100005; int low[N],up[N],p[N],m[N]; int dp[M]; void pack01(int cost,int weight,int V) { for(int v=V;v>=cost;--v) dp[v]=max(dp[v],dp[v-cost]+weight); } void packComplete(int cost,int weight,int V) { for(int v=cost;v<=V;++v) dp[v]=max(dp[v],dp[v-cost]+weight); } void packMultiple(int cost,int weight,int num,int V) { if((num+1)*cost>V) packComplete(cost,weight,V); else { int k=1; while(k<=num) { pack01(cost*k,weight*k,V); num-=k; k=k<<1; } pack01(cost*num,weight*num,V); } } int main() { //freopen("data.in","r",stdin); int n; while(scanf("%d",&n)!=EOF) { int k=0,res=0; for(int i=1;i<=n;++i) { scanf("%d %d %d %d",&p[i],&m[i],&low[i],&up[i]); k+=(0-low[i])*m[i]; res+=(low[i]-0)*p[i]; } memset(dp,0x80,sizeof(dp)); dp[0]=0; for(int i=1;i<=n;++i) packMultiple(m[i],p[i],up[i]-low[i],k); printf("%d\n",dp[k]+res); } return 0; }