题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1260
(http://www.fjutacm.com/Problem.jsp?pid=1382)
题意：给你应付第i个买票人的时间a[i]，以及同时应付相邻两个买票人（i和i-1【i>1】）的时间b[i]，求出最小卖票时间；
思路：这题我想到的方法是用dp1[i]表示第i个人是对其单应付再加上之前一个人为止累加的时间；
dp2[i]则是表示第i个人和第i-1个人是对其一起应付再加上之前累加的时间；
说的有一点乱七八糟，还是看转移方程吧！（我用的转移方程和codevs5318这一题很像）
dp1[i]=Min(dp1[i-1], dp2[i-1])+a[i]; dp2[i]=Min(dp1[i-2], dp2[i-2])+b[i];余下看代码：我也不是很会说明。 1 #include<stdio.h> 2 #include<string.h> 3 const int N = 2020; 4 const int INF = 0x3f3f3f3f; 5 int Min(int a, int b) { 6 return a < b ? a : b; 7 } 8 int dp1[N], dp2[N]={0, INF}; 9 char a[N], b[N]; 10 int main() { 11 int T; 12 scanf("%d", &T); 13 while(T--){ 14 int n; 15 scanf("%d", &n); 16 for(int i=1; i<=n; ++i) 17 scanf("%d", a+i); 18 for(int i=2; i<=n; ++i) 19 scanf("%d", b+i); 20 dp1[1]=a[1]; 21 for(int i=2; i<=n; ++i){ 22 dp1[i]=Min(dp1[i-1], dp2[i-1])+a[i]; 23 dp2[i]=Min(dp1[i-2], dp2[i-2])+b[i]; 24 } 25 int ans=Min(dp1[n], dp2[n]); 26 int s=(ans/3600)+8; 27 printf("d:d:d %s\n", s, (ans/60)%60, ans%60, s>12?"pm":"am"); 28 } 29 }
转载于:https://www.cnblogs.com/DCD112358/p/9019199.html
