7.17 最低票价

题目链接

最低票价

前言

暑假混到了现在，我是一页都没看啊。今天本来也不打算学习了，不过还是要监督自己，将每日一题坚持下来。
明天又是周一，也是我暑假好好学习的第一周

做题情况

未做出来

代码及题解

#include<iostream>

using namespace std;

const int N=380;
int n;
int day[N]; 
int cost[N];
int dp[N]; 


int search(int t, int pos){
    
	
	int i=t;
	
	while(i>=1&&(day[t]-day[i])+1<=pos){
    
		i--;
	}
	
	return i;
} 



int main(){
    
	
	cin>>n;
	
	for(int i=1;i<=n;i++)
		cin>>day[i];
	
	for(int i=1;i<=3;i++)
		cin>>cost[i];	
	
	//设置一个dp数组
	//dp[i]表示前i个旅行所需的最少金额
	
	/* 因此可推出dp公式如下： 1. dp[i]=dp[i-1]+cost[1] 给当天买一张票并仅供当天使用 2. dp[i]=dp[k]+cost[2] 选择某个k，从第k天起的7天内包括第i天 3. dp[i]=dp[k]+cost[3] 选择某个k，从第k天起的30天内包括第i天 对于k的选择：应当选择的k为不包括 最大的一个日期，怎样最大的呢。恰好不在七天/三十天之内的那个日期 可证dp数组是单调递增的 这样的话，比如要求第8天的dp数组，并且采取买7天票的方法，那么就找到第1天，因为第一天的花费在dp[1]中，那么此时可以直接在第二天买，这样就是最优的 */ 
	
	for(int i=1;i<=n;i++){
    
		dp[i]=dp[i-1]+cost[1];	
		dp[i]=min(dp[i],dp[search(i,7)]+cost[2]);
		dp[i]=min(dp[i],dp[search(i,30)]+cost[3]);
	}
	
	cout<<dp[n]<<endl;
	
	return 0;
}