HDU 1260 DP

题

题意：人来排队，一人需要a[i]的时间，与之前人一起需要b[i]的时间，求时间最小值，有输出格式要求。

解

方程：f[i] = min(f[i - 1] + a[i], f[i - 2] + b[i]);
mdzz输出格式大少一个等号调了一天[再见]。

码（1436K, 15ms）

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 2e3 + 1000, INF = 0x3f3f3f3f;
int ff[maxn] = {0}, *f = ff + 5, a[maxn] = {0}, b[maxn] = {0};
inline void write(int n)
{
    if(n >= 10)
        printf("%d", n);
    else
        printf("0%d", n);
}
int main()
{
    int t; read(t);
    while(t--)
    {
        memset(ff, 0, sizeof ff);
        int k; read(k);
        for(int i = 0; i < k; i++) read(a[i]);
        for(int i = 1; i < k; i++) read(b[i]);
        f[0] = a[0];
        for(int i = 1; i < k; i++)
            f[i] = min(f[i - 1] + a[i], f[i - 2] + b[i]);
        int t = f[k - 1], h = 8, m = 0, s = 0;
        h += t / 3600; t %= 3600;
        m += t / 60; t %= 60;
        s += t;
        if(h >= 12 && !(h == 12 && m == 0 && s == 0)) 
            write(h - 12), printf(":"), write(m), printf(":"), write(s), puts(" pm");
        else 
            write(h), printf(":"), write(m), printf(":"), write(s), puts(" am");
    }
    return 0;
}