Codeforces Round #393 (Div. 2) (8VC Venture Cup 2017 - Final Round Div. 2 Edition) D - Travel Card

D - Travel Card

思路：dp，类似于单调队列优化。

其实可以写的更简单。。。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N = 1e5 + ;

const int M = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 +;

int n, t[N], dp[N][], mn[N], a[N];

int st1[N], st2[N], head1, head2, rear1, rear2;

int main() {

    memset(dp, inf, sizeof(dp));

    memset(mn, inf, sizeof(mn));

    mn[] = ;

    scanf("%d", &n);

    for(int i = ; i <= n; i++) {

        scanf("%d", &t[i]);

    }

    dp[][] = ;

    dp[][] = ;

    dp[][] = ;

    st1[rear1++] = ;

    st2[rear2++] = ;

    for(int i = ; i <= n; i++) {

        for(int j = ; j < ; j++) mn[i - ] = min(mn[i - ], dp[i - ][j]);

        dp[i][] = mn[i - ] + ;

        dp[i][] = mn[i - ] + ;

        dp[i][] = mn[i - ] + ;

        while(head1 < rear1 && t[i] - t[st1[head1]] >= ) head1++;

        while(head2 < rear2 && t[i] - t[st2[head2]] >= ) head2++;

        if(head1 < rear1) dp[i][] = min(dp[i][], dp[st1[head1]][]);

        if(head2 < rear2) dp[i][] = min(dp[i][], dp[st2[head2]][]);

        while(head1 < rear1 && dp[i][] < dp[st1[rear1 - ]][]) rear1--;

        while(head2 < rear2 && dp[i][] < dp[st2[rear2 - ]][]) rear2--;

        st1[rear1++] = i;

        st2[rear2++] = i;

    }

    for(int j = ; j < ; j++) {

        mn[n] = min(mn[n], dp[n][j]);

    }

    for(int i = ; i <= n; i++) {

        printf("%d\n", mn[i] - mn[i - ]);

    }

    return ;

}

/*

*/