HDU 1260 Tickets——DP

HDU 1260 Tickets——DP

题意：有n个人来买票，现在知道这n个人买票的时间，以及n-1对人（1和2,2和3...n-1和n）的买票时间，每次你可以选择把一张票卖给一个人或者把两张票卖给相邻的两个人，问你卖完n张票所需要的最短时间

思路：用dp【i】【j】表示前i个人【在第i个人的决策为j】时的最小花费时间，每个状态只有两种决策，即只卖给当前这个人或者卖给当前连续的两个人，所以状态转移方程为：

dp[i][0] = min{dp[i - 1][0] + one[i], dp[i - 1][1]};

dp[i][1] = dp[i  - 1][0] + two[i];

边界的话处理第一个状态（求解时从第二个状态开始）

dp[1][0] = one[1], dp[1][1] = two[1]

处理时间时注意h<12时输出am，否则输出pm（不会出现隔天的情况）

#include #include #include #include using namespace std;const int maxn = 2000 + 10;int T, n, one[maxn], two[maxn], dp[maxn][2];int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &one[i]); for (int i = 1; i <= n - 1; i++) scanf("%d", &two[i]); dp[1][0] = one[1], dp[1][1] = two[1]; for (int i = 2; i <= n; i++) { dp[i][0] = min(dp[i - 1][0] + one[i], dp[i - 1][1]); dp[i][1] = dp[i - 1][0] + two[i]; } int h = 8 + dp[n][0] / 3600; dp[n][0] %= 3600; int m = dp[n][0] / 60; dp[n][0] %= 60; int s = dp[n][0]; char str[10]; if (h < 12) printf("%02d:%02d:%02d am\n", h, m, s); else printf("%02d:%02d:%02d pm\n", h, m, s); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。