ZOJ 2972 Hurdles of 110m 【DP 背包】

Dear 丶 2021-12-10 16:45 324阅读 0赞

一共有N段过程,每段过程里可以选择 快速跑、 匀速跑 和 慢速跑

对于快速跑会消耗F1 的能量, 慢速跑会集聚F2的能量

选手一开始有M的能量,即能量上限

求通过全程的最短时间

定义DP[i][j] 为跨越第 i 个栏,剩余 j 点能量

动态转移方程

  1. dp[i][j] = min(dp[i][j], dp[i-1][j-F1]+T1)   (Fast Mode)
  2. dp[i][j] = min(dp[i][j], dp[i-1][j]+T2)     (Normal Mode)
  3. dp[i][j] = min(dp[i][j], dp[i-1][j+F2]+T3)   (Slow Mode)

Source Code:

  1. //#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
  2. #include <stdio.h>
  3. #include <iostream>
  4. #include <fstream>
  5. #include <cstring>
  6. #include <cmath>
  7. #include <stack>
  8. #include <string>
  9. #include <map>
  10. #include <set>
  11. #include <list>
  12. #include <queue>
  13. #include <vector>
  14. #include <algorithm>
  15. #define Max(a,b) (((a) > (b)) ? (a) : (b))
  16. #define Min(a,b) (((a) < (b)) ? (a) : (b))
  17. #define Abs(x) (((x) > 0) ? (x) : (-(x)))
  18. #define MOD 1000000007
  19. #define pi acos(-1.0)
  20. using namespace std;
  21. typedef long long ll ;
  22. typedef unsigned long long ull ;
  23. typedef unsigned int uint ;
  24. typedef unsigned char uchar ;
  25. template<class T> inline void checkmin(T &a,T b){
  26. if(a>b) a=b;}
  27. template<class T> inline void checkmax(T &a,T b){
  28. if(a<b) a=b;}
  29. const double eps = 1e-7 ;
  30. const int N = 22 ;
  31. const int M = 1100011*2 ;
  32. const ll P = 10000000097ll ;
  33. const int MAXN = 100000 ;
  34. const int INF = 0x3f3f3f3f ;
  35. const int MAX = 10500 ;
  36. struct sc{
  37. int t1, t2, t3, f1, f2;
  38. }a[120];
  39. int n, m;
  40. int dp[120][120];
  41. int main(){
  42. std::ios::sync_with_stdio(false);
  43. int i, j, t, k, l, u, v, x, y, numCase = 0;
  44. cin >> t;
  45. while(t--){
  46. cin >> n >> m;
  47. for(i = 0; i < n; ++i){
  48. cin >> a[i].t1 >> a[i].t2 >> a[i].t3 >> a[i].f1 >> a[i].f2;
  49. }
  50. memset(dp, 0x3f, sizeof(dp));
  51. dp[0][m] = 0;
  52. for(i = 0; i < n; ++i){
  53. for(j = 0; j <= m; ++j){
  54. if(j >= a[i].f1){
  55. checkmin(dp[i + 1][j - a[i].f1], dp[i][j] + a[i].t1);
  56. }
  57. if(j + a[i].f2 > m){
  58. checkmin(dp[i + 1][m], dp[i][j] + a[i].t3);
  59. } else{
  60. checkmin(dp[i + 1][j + a[i].f2], dp[i][j] + a[i].t3);
  61. }
  62. checkmin(dp[i + 1][j], dp[i][j] + a[i].t2);
  63. }
  64. }
  65. int ans = INF;
  66. for(i = 0; i <= m; ++i){
  67. checkmin(ans, dp[n][i]);
  68. }
  69. cout << ans << endl;
  70. }
  71. return 0;
  72. }

转载于:https://www.cnblogs.com/wushuaiyi/p/4326250.html

发表评论

表情:
评论列表 (有 0 条评论,324人围观)

还没有评论,来说两句吧...

相关阅读

    相关 背包】ZJCPC M

    现在还没交题的地方,不知道对不对,但是大概率是对的 这就是个s b背包,赛场上连样例都过不了,还是之后队友硬分类讨论过的 今天写了下一下就过样例了 和比赛的时候写的唯一不

    相关 背包DP | 完全背包问题

    > 完全背包问题:有n种物品,每一件的物品重量为 w\[ i \],价值为 c\[ i \]。现有一个容量为V的背包 (背包的最大承重为V),问如何选取物品放入背包,使得背包内

    相关 ZOJ 3537 区间dp

    题意:给出一些点表示多边形蛋糕的定点的位置(如果蛋糕是凹多边形就不能切),切蛋糕时每次只能在顶点和顶点间切,每一次切蛋糕都有相应的代价,给出代价的公式,问把蛋糕切成多个三角形的