CFR 332 B. Maximum Absurdity ( DP )

Problem - B - Codeforces
題意：
給一個序列，和一個長度 K。求兩個長度 K 的不重疊連續塊最大總和值，若有多解，求下標字典序最小。
解法：
先預處理某個數以後生出一個長度為 K 的連續塊最大總和值。接著枚舉答案左邊塊的右端，並利用前綴和更新答案。

int N, K;
vi A;

void init(){
    cin >> N >> K;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

vi pA;
vi dp;
vi ch;

void preprocess(){
    pA = dp = ch = vi( N + 1 );
    for( int i = 0; i < N; ++i )
        pA[ i + 1 ] = pA[ i ] + A[ i ];
    for( int i = N; i >= 2 * K; --i ){
        if( i == N )
            dp[ i ] = pA[ i ] - pA[ i - K ],
            ch[ i ] = i;
        else{
            dp[ i ] = dp[ i + 1 ];
            ch[ i ] = ch[ i + 1 ];
            if( dp[ i ] <= pA[ i ] - pA[ i - K ] )
                dp[ i ] = pA[ i ] - pA[ i - K ],
                ch[ i ] = i;
        }
    }
}

void solve(){
    int val = 0;
    int lb = -1, rb = -1;
    for( int i = K; i + K <= N; ++i ){
        int u = pA[ i ] - pA[ i - K ] + dp[ i + K ];
        if( val < u )
            val = u,
            lb = i, rb = ch[ i + K ];
    }
    cout << lb - K + 1 << " " << rb - K + 1 << endl;
}