心得：本题分三种情况，首先记录下在某日期使用七天或三十天票的最长延伸日期（不计算用一天票的情况，因为一天票只作用于当天）
情况分以下三种：
1、当前这一天小于最长日期
那么到这一天为止和到上次旅行为止所花金额一样（因为上次也一定小于最长延伸日期，若上次就是使用七天或三十天票那一天，那么相当于这次旅行免费，总费用和上次总费用一样，若上次旅行在使用七天或三十天票那天之后，那么上次和这一天是同等地位的）
2、当前这一天大于最长日期
首先把只买今天票作为默认值，再看看若要保证今天未过期使用七天和三十天票的最晚旅行日期是多少，默认值与用七天票能覆盖今天的最晚旅行日期的上一次旅行总金额+七天票价，用三十天票能覆盖今天的最晚旅行日期的上一次旅行总金额+三十天票价取其中最小值（这个所谓的上一次旅行很重要，WA一个小时就是这里出问题，之前用的是用七天票能覆盖今天的最晚旅行日期总金额+七天票价，这样是错误的转移方程，举一个简单的1,2,8例子就能理解了）

同时更新最长延伸日期

题目描述

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。
在接下来的一年里，你要旅行的日子将以一个名为 days的数组给出。
每一项是一个从1到365的整数。
火车票有三种不同的销售方式：
一张为期一天的通行证售价为 costs[0]美元；
一张为期七天的通行证售价为 costs[1]美元；
一张为期三十天的通行证售价为 costs[2]美元。
通行证允许数天无限制的旅行。

例如，如果我们在第 2天获得一张为期7天的通行证，那么我们可以连着旅行7天：第2天、第3天、4天、第5天、第6天、第7天和第8天。

返回你想要完成在给定的列表 days中列出的每一天的旅行所需要的最低消费。

样例

输入
6
1 4 6 7 8 20
2 7 15

输出
11

算法1

(dp) $O(n^2)$

#include<iostream>
#include<cstring>
using namespace std;

const int N=400;

int day[N],f[N],cost[3],n;
int a[3]={1,7,30};


int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>day[i];
    for(int i=0;i<3;i++) cin>>cost[i];

    int maxsize=day[1];
    f[day[1]]=cost[0];
    for(int i=2;i<=n;i++)
    {
        int j=day[i];
        int k=day[i-1];
        if(j<=maxsize) f[j]=f[k];
        else
        {
            f[j]=f[k]+cost[0];
            for(int u=1;u<3;u++)
            {
                int pre=j-a[u]+1;

                     int l=1,r=i-1;
                        while(l<r)
                        {
                        int mid=(l+r)/2;
                        if(day[mid]>=pre) r=mid;
                        else l=mid+1;
                        }

                        if(day[l]>=pre)
                        {
                            if(cost[u]+f[day[l-1]]<f[j])
                            {
                              maxsize=max(maxsize,a[u]+day[l-1]);
                              f[j]=cost[u]+f[day[l-1]];
                            }
                        }
            }
        }


    }
    cout<<f[day[n]];
    return 0;

}