这道题算是做的第一道需要排序的dp题,太弱了,看了解题报道都半天不懂为什么要按照p-q的顺序排序。。。。
解题思路:与顺序有关的01背包。初看之下似乎和普通背包差不多,判容量大于q时才装。但是这会出大问题,如果一个物品p = 5,q = 7,一个物品p = 5,q = 9,如果先算第一个,那么当次只有7,8...m可以进行状态转移,装第二个物品的时候9,10..m进行转移,第二个物品转移就可以借用第一个物品的那些个状态,而第二个物品先转移,第一个再转移则不能。当然,还有价格有关,当限制一样价格不同时顺序就影响结果。
q-p小的先选。
因为对于物品A p1,q1;B p2,q2 如果q1-p1<q2-p2,那么先选物品A可以推出从q1-p1到M的状态,再选择B物品的时候有些状态就可以从q1-p1到q2-p2这一段中转移过来,反过来显然不可以,会丢失一些状态的转移
code:
/* ID:yueqi LANG:C++ TASK:humble */ #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits.h> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define lson l,m,rt << 1 #define rson m+1,r,rt<<1|1 #define SD(a) scanf("%d",&a) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("humble.in","r",stdin) #define writef freopen("humble.out","w",stdout) const int maxn = 10001; const long long BigP=999983; const long long INF = 0x5fffffff; const int dx[]={-1,0,1,0}; const int dy[]={0,1,0,-1}; const double pi = acos(-1.0); const double eps= 1e-7; using namespace std; struct node{ int p,q,v; }a[501]; int N,M,dp[5001]; bool cmp(const node x,const node y){ return (x.q-x.p)<(y.q-y.p); } int main(){ readf; while(~scanf("%d%d",&N,&M)){ SET(dp,0); FOR(i,1,N) scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v); sort(a+1,a+N+1,cmp); FOR(i,1,N){ FOD(j,M,a[i].p){ if(j>=a[i].q){ dp[j]=max(dp[j],dp[j-a[i].p]+a[i].v); //printf("dp[%d]==%d\n",j,dp[j]); } } } PD(dp[M]);LN; } return 0; }