【题目链接】:

【题意】

去旅行,有3种类型的乘车票;

第一种:只能旅行一次20元

第二种:按时间计算,90分钟内能无限量旅行,50元

第三种:按时间计算,1440分钟内能无限量旅行,120元

每次旅行只消耗一分钟;

给你n次旅行开始的时间(顺序);

让你求出第1到第i次旅行的这些旅行最少需要花费多少钱f[i];

(每次都重新计算)

输出f[i]-f[i-1];

【题解】

动态规划;

设f[i]表示第1..到第i次旅行花费的最少费用;

每一次的旅行,都考虑它是用哪一种票旅行的；

分3种买票方式就好;

对于第一种

只能是前一次旅行转移过来;

第二和第三种;

都尽量往前推;

因为f[i]是∝i的

所以i越小越好;

这个i是由时间决定的即输入的a[i]

用upper_bound来确定最左的位置就好;

转移方程看代码吧

【Number Of WA】

0

【完整代码】

#include 
     
      using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define ps push_back#define fi first#define se second#define rei(x) cin >> x#define ms(x,y) memset(x,y,sizeof x)typedef pair
      
        pii;typedef pair
       
         pll;const int dx[9] = {
    0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {
    0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int N = 1e5+100;int n;int a[N],f[N];int main(){    //freopen("F:\\rush.txt","r",stdin);    ios::sync_with_stdio(false);    rei(n);    rep1(i,1,n)        rei(a[i]);    rep1(i,1,n)    {        f[i] = min(f[i-1]+20,f[upper_bound(a+1,a+1+i,a[i]-90)-a-1]+50);        f[i] = min(f[i],f[upper_bound(a+1,a+1+i,a[i]-1440)-a-1]+120);        cout << f[i]-f[i-1]<