排队买票求最短时间

题目链接

题意：

输入的含义：

第一行表示数据的组数。

第一组数据包括：输入的总人数 n，每个人单独买票花费的时间 （共n个数），每两两之间买票花费的时间（共n-1个数）。

注释：因为第二组数只有一个人，所以输入的数据不存在两两买票的情况，所以比别的情况会少输入一行。

题解：

核心：递推思想

每次选择最短时间：情况一：前k个人的最短时间加上这个人的时间

情况二：前k-1个人的最短时间加上最后这两个人花费的时间

难点：

c[1]=a[1];

for(i=2; i<=n; i++)

{

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

}

#include<bits/stdc++.h>
 using namespace std;
 int main()
 {
     int t;
     scanf("%d",&t);
     while(t--)
     {
         int n,i;
         int a[2002],b[2002],c[2002];
         scanf("%d",&n);
         for(i=1; i<=n; i++)
         {
             scanf("%d",&a[i]);
         }
         for(i=1; i<n; i++)
         {
             scanf("%d",&b[i]);
         }
         c[1]=a[1];
         for(i=2; i<=n; i++)
         {
             c[i]=min(c[i-1]+a[i],c[i-2]+b[i-1]);
         }
         int x,y,z;
         x=c[n]/3600;
         y=c[n]%3600/60;
         z=c[n]%60;
         if(x+8>12)
             printf("%02d:%02d:%02d pm\n",x+8,y,z);
         else
             printf("%02d:%02d:%02d am\n",x+8,y,z);
     }
     return 0;
 }