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-7 ;
const int N = 22 ;
const int M = 1100011*2 ;
const ll P = 10000000097ll ;
const int MAXN = 100000 ;
const int INF = 0x3f3f3f3f ;
const int MAX = 10500 ;
struct sc{
int t1, t2, t3, f1, f2;
}a[120];
int n, m;
int dp[120][120];
int main(){
std::ios::sync_with_stdio(false);
int i, j, t, k, l, u, v, x, y, numCase = 0;
cin >> t;
while(t--){
cin >> n >> m;
for(i = 0; 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[0][m] = 0;
for(i = 0; i < n; ++i){
for(j = 0; j <= m; ++j){
if(j >= a[i].f1){
checkmin(dp[i + 1][j - a[i].f1], dp[i][j] + a[i].t1);
}
if(j + a[i].f2 > m){
checkmin(dp[i + 1][m], dp[i][j] + a[i].t3);
} else{
checkmin(dp[i + 1][j + a[i].f2], dp[i][j] + a[i].t3);
}
checkmin(dp[i + 1][j], dp[i][j] + a[i].t2);
}
}
int ans = INF;
for(i = 0; i <= m; ++i){
checkmin(ans, dp[n][i]);
}
cout << ans << endl;
}
return 0;
}
转载于//www.cnblogs.com/wushuaiyi/p/4326250.html
还没有评论,来说两句吧...