題干：

In the year 2008, the 29th Olympic Games will be held in Beijing. This will signify the prosperity of China and Beijing Olympics is to be a festival for people all over the world as well.

Liu Xiang is one of the famous Olympic athletes in China. In 2002 Liu broke Renaldo Nehemiah's 24-year-old world junior record for the 110m hurdles. At the 2004 Athens Olympics Games, he won the gold medal in the end. Although he was not considered as a favorite for the gold, in the final, Liu's technique was nearly perfect as he barely touched the sixth hurdle and cleared all of the others cleanly. He powered to a victory of almost three meters. In doing so, he tied the 11-year-old world record of 12.91 seconds. Liu was the first Chinese man to win an Olympic gold medal in track and field. Only 21 years old at the time of his victory, Liu vowed to defend his title when the Olympics come to Beijing in 2008.

In the 110m hurdle competition, the track was divided into?N?parts by the hurdle. In each part, the player has to run in the same speed; otherwise he may hit the hurdle. In fact, there are 3 modes to choose in each part for an athlete -- Fast Mode, Normal Mode and Slow Mode. Fast Mode costs the player?T1?time to pass the part. However, he cannot always use this mode in all parts, because he needs to consume?F1force at the same time. If he doesn't have enough force, he cannot run in the part at the Fast Mode. Normal Mode costs the player?T2?time for the part. And at this mode, the player's force will remain unchanged. Slow Mode costs the player?T3?time to pass the part. Meanwhile, the player will earn?F2?force as compensation. The maximal force of a player is?M. If he already has?M?force, he cannot earn any more force. At the beginning of the competition, the player has the maximal force.

The input of this problem is detail data for Liu Xiang. Your task is to help him to choose proper mode in each part to finish the competition in the shortest time.

Input

Standard input will contain multiple test cases. The first line of the input is a single integer?T?(1 <=?T?<= 50) which is the number of test cases. And it will be followed by?T?consecutive test cases.

Each test case begins with two positive integers?N?and?M. And following?N?lines denote the data for the?N?parts. Each line has five positive integers?T1 T2 T3 F1 F2. All the integers in this problem are less than or equal to 110.

Output

Results should be directed to standard output. The output of each test case should be a single integer in one line, which is the shortest time that Liu Xiang can finish the competition.

Sample Input

2 1 10 1 2 3 10 10 4 10 1 2 3 10 10 1 10 10 10 10 1 1 2 10 10 1 10 10 10 10

Sample Output

1 6

Hint

?

For the second sample test case, Liu Xiang should run with the sequence of Normal Mode, Fast Mode, Slow Mode and Fast Mode.

題目大意：

110米欄，運(yùn)動(dòng)員可以用三種狀態(tài)跑，1狀態(tài)耗體力且跑得快，2狀態(tài)不消耗體力，3狀態(tài)恢復(fù)體力且跑得慢。體力上限是M，且初始滿(mǎn)體力，現(xiàn)在想知到最小的時(shí)間跑完全程。

解題報(bào)告：

? ?多階段決策問(wèn)題，考慮dp。dp[i][j]代表前i個(gè)階段，所剩能量為j的最短時(shí)間。

? ? 分情況轉(zhuǎn)移就好了。注意對(duì)于滿(mǎn)狀態(tài)的時(shí)候，不僅可以由“可以使得剛剛好滿(mǎn)狀態(tài)”的狀態(tài)轉(zhuǎn)移過(guò)來(lái)，還可以由中間這些狀態(tài)轉(zhuǎn)移過(guò)來(lái)。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; const int INF = 0x3f3f3f3f; ll n,m; struct Node {int t1,t2,t3,f1,f2; } p[MAX]; int dp[155][155];//第i個(gè)階段 還剩j能量 的最短時(shí)間 int main() {int t;cin>>t;while(t--) {cin>>n>>m;for(int i = 1; i<=n; i++) {scanf("%d%d%d%d%d",&p[i].t1,&p[i].t2,&p[i].t3,&p[i].f1,&p[i].f2);}memset(dp,INF,sizeof dp);//?????????????????????dp[0][m] = 0;for(int i = 1; i<=n; i++) {for(int j = 0; j<=m; j++) {//勻速 dp[i][j] = min(dp[i][j],dp[i-1][j] + p[i].t2);//加速 if(j+p[i].f1 <=m) dp[i][j] = min(dp[i][j],dp[i-1][j+p[i].f1] + p[i].t1);//減速if(j == m) {for(int k = max(0,j-p[i].f2); k<=m; k++) {dp[i][j] = min(dp[i][j],dp[i-1][k] + p[i].t3);}}else if(j-p[i].f2 >= 0) dp[i][j] = min(dp[i][j],dp[i-1][max(j-p[i].f2,0)] + p[i].t3);}}int ans = INF;for(int j = 0 ; j<=m; j++) ans = min(ans,dp[n][j]);printf("%d\n",ans);}return 0 ; } /* 1 1 4 10 5 3 10 10*/

?

總結(jié)

以上是生活随笔為你收集整理的【ZOJ - 2972】Hurdles of 110m （dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。