题解：P17114 [Algo Beat 009 & MROI-R1] Payment

· · 题解

dp 好题。

思路

贪心一下，不难发现两个乘车段结算一次最优。

设 dp_i 为前 i 个乘车段的最小花费。

初始状态：dp_0=0，dp_1=a_1，dp_2=\min\{a_1,a_2\}。其余为无穷大。

转移方程：

dp_i=\min\{dp_{i-1}+a_i,dp_{i-2}+\min\{a_{i-1},a_i\}\}

答案：dp_n。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=8e6+10;
int n;
int a[N];
int dp[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    memset(dp,0x3f,sizeof dp); // 初始化为无穷大
    dp[0]=0;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    dp[1]=a[1];
    dp[2]=min(a[1],a[2]);
    for(int i=3;i<=n;++i){
        dp[i]=min(dp[i-1]+a[i],dp[i-2]+min(a[i-1],a[i])); // 转移
    }
    cout<<dp[n]; // 答案
    return 0;
}