HDU-1260 Tickets

感觉题目还是比较水的，我这个蒟蒻也能写出来hh。

思路：f[i]是前i个人（包含第i个）买票需要花费的总时间，第i个人买票所需时间，可以自己单买（f[i - 1] + a[i])，也可以和前面那个人拼团hh（f[i - 2] + to[i]），前提是他前面得有人才行(i >= 2)。

方程为f[i] = min(f[i - 1] + a[i], f[i - 2] + to[i])。

直接看代码吧。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int N = 2010;
 5 
 6 int n;
 7 //第i个人单卖和第i个人和前一个人一起卖
 8 int a[N], to[N];
 9 int f[N];
10 
11 int main() {
12 　　int t;
13 　　cin >> t;
14 　　while(t--) {
15 　　cin >> n;
16 　　for(int i = 1; i <= n; i++) cin >> a[i];
17 　　for(int i = 2; i <= n; i++) cin >> to[i];
18 　　f[0] = 0;
19 　　for(int i = 1; i <= n; i++) {
20 　　f[i] = f[i - 1] + a[i];
21 　　if(i >= 2) f[i] = (f[i] <= f[i - 2] + to[i] ? f[i] : f[i - 2] + to[i]);
22 　　}
23 　　int tol = 8 * 3600 + f[n];
24 　　int h = tol / 3600;
25 　　tol -= tol / 3600 * 3600;
26 　　int m = tol / 60;
27 　　tol -= tol / 60 * 60;
28 　　int s = tol;
29 　　if(h < 12) {
30 　　　　if(h < 10)
31 　　　　cout << 0;
32 　　　　cout << h << ":";
33 
34 　　　　if(m < 10)
35 　　　　cout << 0;
36 　　　　cout << m << ":";
37 　　　　if(s < 10)
38 　　　　cout << 0;
39 　　　　cout << s << " am" << endl;
40 　　}
41 　　else {
42 　　　　cout << h << ":";
43 
44 　　　　if(m < 10)
45 　　　　cout << 0;
46 　　　　cout << m << ":";
47 　　　　if(s < 10)
48 　　　　cout << 0;
49 　　　　cout << s << " pm" << endl;
50 　　　}
51 　　}
52 　　return 0;
53 }