Tickets HDU - 1260

输入：T：测试组数    K：人数  K个：每个人的买票时间  K-1个：相邻人的买票花费时间

题意：告诉你每个人的买票时间和相邻两个人的买票时间，求N个人最少可以用多少秒完成 。   售票员很想早点回家啊

这题加深了我对DP的理解，题目要我们求N个人时候的最短时间，那么我们设dp[n]，假象dp[n]是所求解,那么有dp[n]=min{dp[n-1]+a[n],dp[n-2]+b[n]}; 那么我们求dp[n] 就要求出dp[n-1]的最小值和dp[n-2]的最小值，那么根据递推式dp[n]=min{dp[n-1]+a[n],dp[n-2]+b[n]}其中n必须大于等于3才能满足条件，我是从1开始读取数据，我们可以求出dp[n-1]和dp[n-2]的最小值，依次类推，我们只要求出dp[1],dp[2] 就可以求出dp[n] 的最小值。从最优解的分析角度来说，因为每一个都是最小值，满足最优子解的条件。从无后效性角度来说，我前n的决策和第n以后的决策无关，前n决策影响第n个决策，但只能通过第n个决策去影响后面 >n 的决策。

接下来是一个时间处理的操作，已知秒数t，就有H=t/3600  ,  minute= t%3600 / 60   ,  s=t%60 ,   以及%02补0操作。  有一个细节是k=1的情况下，要特别处理

。思路想通了就GET OVER IT ！

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define MAXN 2000+5

int dp[MAXN];

int a[MAXN];

int b[MAXN];

using namespace std;

int main(void)

{

         intt;

         cin>> t;

         while(t--)

         {

                   intk;

                   cin>> k;

                   for(inti=1;i<=k;i++)

                            scanf("%d",a+i);

                   if(k==1)

                   {

                            printf("%02d:%02d:%02dam\n",8,0,a[1]);

                            continue;

                   }

                   for(inti=1;i<=k-1;i++)

                            scanf("%d",b+1+i);

                   dp[1]=a[1];

                   dp[2]=min(a[1]+a[2],b[2]);

                   /*if(k==2)

                   {

                            printf("%d\n",dp[2]);

                            continue;

                   }*/

                   for(inti=3;i<=k;i++)

                   {

                            dp[i]=min(dp[i-1]+a[i],dp[i-2]+b[i]);

                   }

                   intcost=dp[k];

                   intm=dp[k]%3600/60;

                   inth=dp[k]/3600;

                   ints=dp[k]%60;

                   if(h+8> 12)

                   {

                            printf("%02d:%02d:%02dpm\n",h+8-12,m,s);

                   }

                   else

                   {

                            printf("%02d:%02d:%02dam\n",h+8,m,s);

                   }

         }

}

通过这道题，我GET了什么？

1.分析DP问题的方法

2.对时间操作，把秒数变成小时分钟秒的方法 以及 补0

集训第五天 Fighting!!!