Jesus, what a great movie! Thousands of people are rushing to the cinema. However, this is really a tuff time for Joe who sells the film tickets. He is wandering when could he go back home as early as possible.
A good approach, reducing the total time of tickets selling, is let adjacent people buy tickets together. As the restriction of the Ticket Seller Machine, Joe can sell a single ticket or two adjacent tickets at a time.
Since you are the great JESUS, you know exactly how much time needed for every person to buy a single ticket or two tickets for him/her. Could you so kind to tell poor Joe at what time could he go back home as early as possible? If so, I guess Joe would full of appreciation for your help.
A good approach, reducing the total time of tickets selling, is let adjacent people buy tickets together. As the restriction of the Ticket Seller Machine, Joe can sell a single ticket or two adjacent tickets at a time.
Since you are the great JESUS, you know exactly how much time needed for every person to buy a single ticket or two tickets for him/her. Could you so kind to tell poor Joe at what time could he go back home as early as possible? If so, I guess Joe would full of appreciation for your help.
InputThere are N(1<=N<=10) different scenarios, each scenario consists of 3 lines:
1) An integer K(1<=K<=2000) representing the total number of people;
2) K integer numbers(0s<=Si<=25s) representing the time consumed to buy a ticket for each person;
3) (K-1) integer numbers(0s<=Di<=50s) representing the time needed for two adjacent people to buy two tickets together.
OutputFor every scenario, please tell Joe at what time could he go back home as early as possible. Every day Joe started his work at 08:00:00 am. The format of time is HH:MM:SS am|pm.
Sample Input
2 2 20 25 40 1 8
Sample Output
08:00:40 am 08:00:08 am
这题是道基础题，但让我对dp又有了更深的理解，所以记录一下。
之前想这道题，想到是对每个人的状态进行判断，即两种情况，一是和上一个人组队，二是自己一个人排队。
但是我想的是用dp数组记录每个数最佳的状态，但发现很难想，自己写试试，也写不下去。
看了题解，发现题解都是用dp数组记录最小的时间和，设当前数为i，如果i上一个人组队为u，则dp[i]=dp[i-2]+nus[i];
(nus数组记录的是两人组队的时间）如果i不和上一个人组队，自己单独排，则dp[i]=dp[i-1]+nu[i];
这两种情况，选哪种取决于哪种时间最低。
就是这么简单，我就没推出来 T T。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int M = 2222; 6 int nu[M],nus[M],dp[M]; 7 int main(){ 8 int n; 9 scanf("%d",&n); 10 while(n--){ 11 memset(dp,0,sizeof(dp)); 12 memset(nu,0,sizeof(nu)); 13 memset(nus,0,sizeof(nus)); 14 int k; 15 scanf("%d",&k); 16 for(int i=1;i<=k;i++){ 17 scanf("%d",&nu[i]); 18 } 19 for(int i=2;i<=k;i++){ 20 scanf("%d",&nus[i]); 21 } 22 dp[0]=0;dp[1]=nu[1]; 23 for(int i=2;i<=k;i++){ 24 dp[i]=min(dp[i-1]+nu[i],dp[i-2]+nus[i]); 25 } 26 int h=dp[k]/3600+8; 27 int m=dp[k]/60%60; 28 int s=dp[k]%60; 29 printf("%02d:%02d:%02d am ",h,m,s); 30 } 31 return 0; 32 }