[PKU/POJ][2392][Space Elevator][多重背包]

darren_nizna

先将数据按 a_i 从小到大排序，然后直接背包。。

#include <iostream>#include <algorithm>#include <cstdio>#include <cstdlib>#include <cstring>struct Node{int h_i, a_i, c_i;};bool operator<( Node a, Node b ){return a.a_i< b.a_i; }Node dat[410];int  dp[40010], n, num[40010];int main(){scanf("%d",&n );for( int i= 1; i<= n; ++i )scanf("%d%d%d", &dat[i].h_i, &dat[i].a_i, &dat[i].c_i );std::sort( dat+ 1, dat+ 1+ n );for( int i= 0; i<= 40000; ++i ) dp[i]= 0; dp[0]= 1;for( int i= 1; i<= n; ++i ){for( int j= 0; j<= dat[i].a_i; ++j ) num[j]= 0;for( int j= dat[i].h_i; j<= dat[i].a_i; ++j )if( !dp[j] && dp[ j- dat[i].h_i ] && num[ j- dat[i].h_i ]< dat[i].c_i ){dp[j]= 1; num[j]= num[ j- dat[i].h_i ]+ 1;}}int k= 40000;while( k && !dp[k] ) k--;printf("%d\n", k );return 0;}