hdu1260 DP

题意：现在有n个人要买电影票，如果知道每个人单独买票花费的时间，还有和前一个人一起买花费的时间，问最少花多长时间可以全部买完票。
刚学DP，就从简单的开始做起，从这道题我们可以知道，每个人只有三种情况，如下图，f[i][1/2/3]表示第i个人选择哪种购买方式所能得到最少的钱。
解释下转移方程，因为如果那个人选择了自己买，那么知道这个人所能获得的最少价值就是前面一个人（i-1）个人选择他自己买，或者选择和前面的人一起买的最少价值,再加上i这个人自己买的价值。
所以f[i][1] = min(f[i-1][1],f[i-1][2])+v[i];
先说下第三种，就是当前的人跟后面的人一起买，所以他的价值就是前面一个人选择自己买，或者跟他前面的人一起买的最低价值。
所以f[i][3] = min(f[i-1][1],f[i-1][2])+vv;(vv就是i这个人和后面那个人一起买的价值）
如果这个人选择跟前面的人一起买，那么因为我们在f【i-1】[3]的情况已经算好了他和后面人一起买的钱所以直接转移就好
就是f[i][2] = f[i-1][3];
最后答案就是min(f[n][1],f[n][2]),为什么没有f[n][3]？因为最后一个人无法跟后面的人一起买。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
#include<stack>
#define ll long long
using namespace std;
const long long max_ = 2e3 + 7;
inline int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
int f[max_][4],value[max_], qianvale[max_];
void output(int num) {
	if (num >= 10) {
		cout << num;
	}
	else {
		cout << "0" << num;
	}
}
int main() {
	int T = read();
	while (T--) {
		int n = read();
		for (int i = 1; i <= n; i++) {
			value[i] = read();
		}
		qianvale[1] = value[1];
		for (int i = 2; i <= n; i++) {
			qianvale[i] = read();
		}
		for (int i = 0; i <= n+1; i++)
			for (int j = 0; j <= 3; j++)
				f[i][j] = 1e9;
		f[0][2] = 0;
		f[0][1] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= 3; j++) {
				if (j == 1) {
					f[i][1] = min( f[i - 1][2], f[i - 1][1])+value[i];
				}
				if (j == 2) {
					if(i>1)
					f[i][2] =  f[i - 1][3] ;
				}
				if (j == 3) {					
					f[i][3] =  qianvale[i+1] + min(f[i-1][1],f[i-1][2]);
				}
			}
		}
		int ans = min(f[n][1], f[n][2]);
		int shi, fen = ans / 60, miao = ans % 60;
		shi = fen / 60+8;
		fen = fen % 60;
		if (shi >= 12) {
			output(shi); cout << ":";
			output(fen); cout << ":";
			output(miao); cout << " pm\n";

		}
		else {
			output(shi); cout << ":";
			output(fen); cout << ":";
			output(miao); cout << " am\n";
		}
		for (int i = 0; i <= n + 1; i++)
			for (int j = 0; j <= 3; j++)
				f[i][j] = 1e9;
		memset(value, 0, sizeof(value));
		memset(qianvale, 0, sizeof(qianvale));

	}
	return 0;
}