可以看成01背包问题
//题意：求取列车公司最大利润，对于某一区间的车票要拒则全拒。求如何运载盈利最大
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cctype> 4 #include <cstring> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <algorithm> 12 #include <iostream> 13 using namespace std; 14 typedef long long ll; 15 int n, m, k, ans; 16 int step[25]; 17 struct ND 18 { 19 int x, y; 20 int num; 21 }st[25]; 22 23 inline bool judge( int x ) 24 { 25 for( int i = st[x].x; i < st[x].y; ++i ) 26 if( st[x].num + step[i] > n ) 27 return false; 28 return true; 29 } 30 31 void dfs( int x, int num ) 32 { 33 if( x >= k ) 34 { 35 if( num > ans ) 36 ans = num; 37 return; 38 } 39 if( judge( x ) ) 40 { 41 for( int i = st[x].x; i < st[x].y; ++i ) 42 step[i] += st[x].num; 43 dfs( x+1, num+( st[x].y - st[x].x ) * st[x].num ); 44 for( int i = st[x].x; i < st[x].y; ++i ) 45 step[i] -= st[x].num; 46 } 47 dfs( x+1, num ); 48 } 49 50 int main() 51 { 52 while( ~scanf( "%d%d%d", &n, &m, &k ) && n+m+k ) 53 { 54 ans = 0; 55 memset( step, 0, sizeof( step ) ); 56 for( int i = 0; i < k; ++i ) 57 scanf( "%d%d%d", &st[i].x, &st[i].y, &st[i].num ); 58 dfs( 0, 0 ); 59 printf( "%d ", ans ); 60 } 61 return 0; 62 }