[PKU/POJ][2392][Space Elevator][多重背包]
先将数据按 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;intdp, n, num;int main(){scanf("%d",&n );for( int i= 1; i<= n; ++i )scanf("%d%d%d", &dat.h_i, &dat.a_i, &dat.c_i );std::sort( dat+ 1, dat+ 1+ n );for( int i= 0; i<= 40000; ++i ) dp= 0; dp= 1;for( int i= 1; i<= n; ++i ){for( int j= 0; j<= dat.a_i; ++j ) num= 0;for( int j= dat.h_i; j<= dat.a_i; ++j )if( !dp && dp[ j- dat.h_i ] && num[ j- dat.h_i ]< dat.c_i ){dp= 1; num= num[ j- dat.h_i ]+ 1;}}int k= 40000;while( k && !dp ) k--;printf("%d\n", k );return 0;}
页:
[1]