本文共 1933 字，大约阅读时间需要 6 分钟。

DP - Tickets - HDU - 1260

题意：

现在有n个人要买电影票，如果知道每个人单独买票花费的时间，还有和前一个人一起买花费的时间，问最少花多长时间可以全部买完票。

输入：

$T组测试样例，$

$每组包括一个正整数n，表示排队的人数$

$接着n个正整数，表示每个人单独买票的时间s_i$

$最后n-1个正整数，表示每个人与前一个人一起买票花费的时间t_i，i\ge 2$

Sample Input

2220 254018

Sample Output

08:00:40 am08:00:08 am

数据范围：

$1\le T\le 10,1\le n\le 2000,0s\le S_i\le 25s,0s\le t_i\le 50s$

分析：

$对于每个人而言，要么单独购买，要么与前一个人一起购买。$

$记f[i]:表示前i个人购票的最少时间。$

$第i个人单独购买的最少花费：f[i]=f[i-1]+s[i]$

$第i个人与前一个人一起购买的最小花费：f[i]=f[i-2]+t[i]$

$状态转移方程在二者中取较小值。$

$经计算，排队最多耗时5000s<2h，因此我们不需要担心时间从上午到下午。$

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int N = 2010;int f[N], n;int T;int s[N], t[N];int main(){          scanf("%d",&T);    while(T--)    {           scanf("%d",&n);        for(int i=1;i<=n;i++) scanf("%d",&s[i]);        for(int i=2;i<=n;i++) scanf("%d",&t[i]);        f[1] = s[1];        for(int i=2;i<=n;i++) f[i]=min(f[i-1]+s[i], f[i-2]+t[i]);        int sum = f[n];        int h = sum/3600, m = (sum%3600)/60, sec = sum%60;        h+=8;        printf("%02d:%02d:%02d am\n",h,m,sec);    }    return 0;}