【题解】[Algo Beat 009 & MROI-R1] Payment
zsTree
·
·
题解
刚开始用的贪心，我是 /bangbangt（）
显然是 DP。
状态设计
$dp_{i,1}$ 表示坐前 $i$ 次地铁，第 $i$ 次继续延续第 $i-1$ 次的乘车记录能得到的最大减免总和。
**转移方程**
新开的乘车记录是没有减免贡献的，所以直接继承：
$$
dp_{i,0}=dp_{i-1,1}
$$
如果延续第 $i-1$ 的乘车记录，可以从新开的乘车记录开始继承，也可延续原来的乘车记录，两者取 $\max$ 即可：
$$
dp_{i,1} = \max\big(dp_{i-1,0} + \max(a_{i-1}, a_i),\ dp_{i-1,1}\big)
$$
因为 $dp_{i,1}$ 是从 $dp_{i-1,0}$ 推导来的，已经免过一个 $\max(a_{i-1},a_i)$，所以上面式子的 $dp_{i-1,1}$ 不需要再去加 $\max$ 了。
由于转移过程中只涉及 $i$ 与 $i-1$ 次的状态，可以把第一维滚掉。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[2];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
int a, b;
int sum = 0;
if (n >= 1) {
cin >> a;
sum += a;
}
for (int i = 2; i <= n; i++) {
cin >> b;
sum += b;
int tmp = dp[0];
dp[0] = dp[1];
dp[1] = max(tmp + max(a, b), dp[1]);
a = b;
}
cout << sum - dp[1];
return 0;
}
```