CF466A Cheap Travel 题解

一只大龙猫 · 2021-06-10 19:49:46 · 题解

原题传送门

题意：

• 有两种地铁票，单程票一张价格为 a，m 程票一张价格为 b。

• 给定 n,m,a,b，求搭乘 n 次地铁的最低花费。

• 数据范围：1\leqslant n,m,a,b \leqslant1000。

看了一下大家的题解，发现没有人用动规。我就来写一下吧。

设 f(i) 为搭 i 次地铁的最少花费，则易推出转移方程：

• 若 i \geqslant m，则 f(i)= \min (f(i-1)+a,f(i-m)+b)。

• 否则 f(i)= \min (f(i-1)+a,b)。

为什么转移方程的第二条不是 f(i)=f(i-1)+a？考虑最极端的情况，b=a+1 且 3\leqslant n \leqslant m，显然此时买一张 m 程票要比买 n 张单程票要便宜。

综上，便不难写出代码：

#include<iostream>
using namespace std;
int f[2000],n,m,b,a;
int main(){
    cin>>n>>m>>a>>b;
    for(int i=1;i<=n;i++){
        if(i>=m)f[i]=min(f[i-1]+a,f[i-m]+b);
        else f[i]=min(f[i-1]+a,b);
    }
    cout<<f[n];
    return 0;
}