Codeforces Round #393 (Div. 2) D. Travel Card DP

D. Travel Card

链接：

http://codeforces.com/contest/760/problem/D

题意：

乘坐电车，一共会有n次乘坐，之后n行会一次给出每次乘坐的时间。问你最少花的钱是多少。每次输出应该支付的钱。

题解：

用dp[n]表示第n次旅行一共所要花费的最小钱数。那么对于dp[n]

1.就是花20快钱买咯。

2.和上面的一起能凑个90分钟就凑个90分钟。

3.和上面的一起能凑个一天就凑个1天。

那么当前的值就是这3个值的最小值。

然后看看代码就懂了。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 1e5 + 7;
 7 int t[maxn];
 8 int dp[maxn];
 9 
10 int main()
11 {
12     int n;
13     scanf("%d", &n);
14     for (int i = 1; i <= n; i++) scanf("%d", t + i);
15     int sum = 0;
16     for (int i = 1; i <= n; i++) {
17         dp[i] = dp[i - 1] + 20;
18         for (int j = i - 1; j >= 1; j--) {
19             if (t[i] - t[j] < 90) dp[i] = min(dp[i], dp[j - 1] + 50);
20             else if (t[i] - t[j] < 1440) dp[i] = min(dp[i], dp[j - 1] + 120);
21             else break;
22         }
23         printf("%d
", dp[i] - sum);
24         sum = dp[i];
25     }
26     return 0;
27 }