Hurdlesof110mZOJ2972（简单DP）

#include
using namespace std;
struct node
{int t1,t2,t3;int f1,f3;
}s[115];
const int INF&＃61;0x3f3f3f3f;
int dp[115][115];//对于跑第i段的时候相对应的精力为j的时候dp[i][j]表示的是时间最短的
int main()
{int t;scanf("%d",&t);while(t--){int n,m;scanf("%d %d",&n,&m); for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d %d %d %d %d",&s[i].t1,&s[i].t2,&s[i].t3,&s[i].f1,&s[i].f3);for(int i&＃61;1;i<&＃61;110;i&＃43;&＃43;){for(int j&＃61;0;j<&＃61;110;j&＃43;&＃43;)dp[i][j]&＃61;INF;}//初始化为最大 然后在慢慢的变化就是这个样子的 int k;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;m;j>&＃61;0;j--){//表示中速跑步前一段没有变化dp[i][j] &＃61; min(dp[i][j],dp[i-1][j]&＃43;s[i].t2);//表示高速度跑步 if(j>&＃61;s[i].f1)dp[i][j-s[i].f1] &＃61; min(dp[i][j-s[i].f1],dp[i-1][j]&＃43;s[i].t1);//表示慢速度跑步int sum&＃61; j&＃43;s[i].f3;if(sum>m) sum&＃61;m;dp[i][sum] &＃61; min(dp[i][sum],dp[i-1][j]&＃43;s[i].t3); } }int minn&＃61;INF;/* for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;0;j<&＃61;m;j&＃43;&＃43;)printf("%d ",dp[i][j]);cout<}Comment in Markdown