题目描述
有三种通行证
一种覆盖一天
一种覆盖七天
一种覆盖三十天
有n天需要有通行证
问n天安排完至少多少钱
输入
先输入n
然后输入需要通行证的n天
最后输入三种通行证的价格
输出
至少多少钱
DP思路
f[i]代表安排完第i天(1≤i≤365)至少多少钱
如果第i天不需要通行证,可以直接赋值为f[i-1]
否则在
1.直接买一天的(f[i-1]+第一种通行证价格)
2.在第i-7+1天买覆盖7天的(f[i-6]+第二种通行证价格)
3.在第i-30+1天买覆盖30天的(f[i-29]+第三种通行证价格)
中取最小值
注意:i不够七天或三十天也是可以买任意通行证的,
所以减完后结果要和0取max
C++ 代码
#include<iostream>
using namespace std;
int f[370],costs[3]; //f数组和三种通行证价格
bool must[370]; //是否需要通行证
int main(){
int n;
scanf("%d",&n);
while(n--){
int x;
scanf("%d",&x);
must[x]=1;
}
scanf("%d%d%d",&costs[0],&costs[1],&costs[2]);
for(int i=1;i<=365;i++)
if(must[i]){ //必须有通行证
f[i]=f[i-1]+costs[0];
f[i]=min(f[i],f[max(i-7,0)]+costs[1]);
f[i]=min(f[i],f[max(i-30,0)]+costs[2]);
}
else //不需要通行证
f[i]=f[i-1];
printf("%d",f[365]);
return 0;
}