题目给出两种状态的转化方式,所以这题可以用DP来做
f[i]
:当前库存可乐有i瓶,想要使得库存可乐数量不低于$n\times m$瓶的所有方案的花费最小值
状态转移:f[i] = min(f[i + 1] + d,f[min(i + n,n * m)] + c)
-
第一个应该可以理解,对应题目中
单瓶:d 元/瓶。
-
第二个考虑到
i + n
会大于n * m
,所以取min,因为当i
大于n * m
与等于n * m
,f[i]
都是0
DP $O(n \times m - k)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int f[N];
int c,d,n,m,k;
int main()
{
cin >> c >> d >> n >> m >> k;
if(k >= n * m) puts("0");
else
{
f[n * m] = 0;
for(int i = n * m - 1;i >= k;i --)
f[i] = min(f[i + 1] + d,f[min(i + n,n * m)] + c);
cout << f[k];
}
}
记忆化搜索
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int f[N];
int c,d,n,m,k;
int dp(int x)
{
if(x >= n * m) return 0;
if(~f[x]) return f[x];
return f[x] = min(dp(x + 1) + d,dp(x + n) + c);
}
int main()
{
cin >> c >> d >> n >> m >> k;
if(k >= n * m) puts("0");
else
{
for (int i = k; i < n * m; i ++ ) f[i] = -1;
cout << dp(k);
}
}