poj2392 Space Elevator

思路：

排序+dp。

实现：

1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 const int INF = 0x3f3f3f3f; 8 9 int K, dp[405][40005]; 10 struct node 11 { 12 int h, a, n; 13 }; 14 node a[405]; 15 16 bool cmp(const node & x, const node & y) 17 { 18 return x.a < y.a; 19 } 20 21 int solve() 22 { 23 for (int j = 0; j <= 40000; j++) 24 { 25 dp[K][j] = j; 26 } 27 for (int i = K - 1; i >= 0; i--) 28 { 29 for (int j = 0; j <= 40000; j++) 30 { 31 dp[i][j] = -INF; 32 for (int t = 0; t <= a[i].n; t++) 33 { 34 if (j + t * a[i].h > a[i].a) 35 break; 36 dp[i][j] = max(dp[i][j], dp[i + 1][j + t * a[i].h]); 37 } 38 } 39 } 40 return dp[0][0]; 41 } 42 43 int main() 44 { 45 cin >> K; 46 for (int i = 0; i < K; i++) 47 { 48 cin >> a[i].h >> a[i].a >> a[i].n; 49 } 50 sort(a, a + K, cmp); 51 cout << solve() << endl; 52 return 0; 53 }

 

转载于:https://www.cnblogs.com/wangyiming/p/6574641.html

总结

以上是生活随笔为你收集整理的poj2392 Space Elevator的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。