ZOJ 2972 Hurdles of 110m 【DP 背包】

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

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

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

求通过全程的最短时间

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

动态转移方程

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

Source Code:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0)using namespace std;typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ;template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}
template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;}const double eps = 1e- ;
const int N = ;
const int M = * ;
const ll P = 10000000097ll ;
const int MAXN = ;
const int INF = 0x3f3f3f3f ;
const int MAX = ;struct sc{
int t1, t2, t3, f1, f2;
}a[];int n, m;
int dp[][];int main(){
std::ios::sync_with_stdio(false);
int i, j, t, k, l, u, v, x, y, numCase = ;
cin >> t;
while(t--){
cin >> n >> m;
for(i = ; i < n; ++i){
cin >> a[i].t1 >> a[i].t2 >> a[i].t3 >> a[i].f1 >> a[i].f2;
}
memset(dp, 0x3f, sizeof(dp));
dp[][m] = ;
for(i = ; i < n; ++i){
for(j = ; j <= m; ++j){
if(j >= a[i].f1){
checkmin(dp[i + ][j - a[i].f1], dp[i][j] + a[i].t1);
}
if(j + a[i].f2 > m){
checkmin(dp[i + ][m], dp[i][j] + a[i].t3);
} else{
checkmin(dp[i + ][j + a[i].f2], dp[i][j] + a[i].t3);
}
checkmin(dp[i + ][j], dp[i][j] + a[i].t2);
}
}
int ans = INF;
for(i = ; i <= m; ++i){
checkmin(ans, dp[n][i]);
}
cout << ans << endl;
} return ;
}