poj2392 Space Elevator（多重背包转化为完全背包与01背包）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
struct node{
int a,b,c;
}a[430];
int dp[40500];
bool cmp(node a,node b){
return a.b<b.b;
}
int main(){
int k;cin>>k;
for(int i=1;i<=k;i++){
scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
}
sort(a+1,a+1+k,cmp);
for(int i=1;i<=k;i++){
if(a[i].b>a[i].c*a[i].a){
for(int n=1;n<a[i].c;n*=2){
for(int v=a[i].b;v>=a[i].a*n;v--){
dp[v]=max(dp[v],dp[v-a[i].a*n]+a[i].a*n);
}
a[i].c-=n;
}
if(a[i].c>0){
for(int v=a[i].b;v>=a[i].a*a[i].c;v--)
dp[v]=max(dp[v],dp[v-a[i].a*a[i].c]+a[i].a*a[i].c);
}
}
else{
for(int v=a[i].a;v<=a[i].b;v++){
dp[v]=max(dp[v],dp[v-a[i].a]+a[i].a);
}
}
}
int ans=0;
for(int i=1;i<=a[k].b;i++) ans=max(ans,dp[i]);
cout<<ans<<endl;
}