ZJOI2006 황제의 고민 2점+DP

전송문
처음 문제를 보니 마치 물문제인 것 같았어요. 짝짓기를 판정하면 돼요. 시험을 다 보고 나서 알았어요. 절강의 문제 헤헤 결국 모의경기는 20밖에 못 땄어요.
문제풀이: 2점 답안, 체크할 때 DP, 맥스[i] M ax[i]를 제 i 개인이 가장 많고 제 1 개인 훈장과 같은 개수, 민[i] M i n[i]를 제 i 개인이 가장 적고 제 1 개인 훈장과 같은 개수로 설정하면

Max[i]=min(a[i],a[1]−Min[i−1]) M a x [ i ] = m i n ( a [ i ] , a [ 1 ] − M i n [ i − 1 ] )

Min[i]=max(0ll,a[i]−(t−(a[1]+a[i−1]−Max[i−1]))) M i n [ i ] = m a x ( 0 l l , a [ i ] − ( t − ( a [ 1 ] + a [ i − 1 ] − M a x [ i − 1 ] ) ) )

민[n] M i n [n]이 0인지 아닌지 판정하면 끝인데... 낙곡의 문제풀이에는 O(n) O(n)가 있는 것 같은데, 난 못 알아봤어.

#include
#include
#include
using namespace std;
const int MAXN = 30001;

int a[MAXN], n;
int Max[MAXN], Min[MAXN];

inline int read(){
    int k = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){k = k*10 + ch - '0'; ch = getchar();}
    return k * f;
}

bool check(int t){
    memset(Max, 0, sizeof(Max));
    memset(Min, 0x3f, sizeof(Min));
    Max[1] = Min[1] = a[1];
    for(int i = 2; i <= n; i++){
        Max[i] = min(a[i], a[1] - Min[i - 1]);
        Min[i] = max(0, a[i] - (t - (a[1] + a[i - 1] - Max[i - 1])));
    }
    return Min[n] == 0;
}

int main(){
    n = read();
    int l = 0, r = 0, mid;
    for(int i = 1; i <= n; i++){
        a[i] = read();
        r += a[i];
    }
    a[n + 1] = a[1];
    while(l <= r){
        mid = (l + r) >> 1;
        if(check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    for(int i = 1; i <= n; i++){
        l = max(l, a[i] + a[i + 1]);
    }

    printf("%d", l);
    return 0;
}