2479:Maximum sum

PKU

keyword

動的計画法　C++

概要

長さn(<10^5)の数列が与えられる。このとき、max_{1<=s1<=t1

  • 数字を1個も拾っていない。
  • 一つ目の区間の中にいる。
  • 一つ目の区間は終えていて二つ目の区間に入っていない。
  • 二つ目の区間の中にいる。
  • 二つ目の区間を抜けた。
#define CHECK(j) (dp[i][j]!=-1<<30)

int main(){
    int ns[50001], dp[50001][5];
    int i, j, n, rept;
    rept = readint();

    while(rept--){
        n = readint();
        REP(i,n) ns[i] = readint();
        REP(i,n+1)REP(j,5) dp[i][j] = -1<<30;
        dp[0][0] = 0;
        REP(i,n){
            if(CHECK(0)){
                if(dp[i+1][0] < dp[i][0]) dp[i+1][0] = dp[i][0];
                if(dp[i+1][1] < dp[i][0]+ns[i]) dp[i+1][1] = dp[i][0]+ns[i];
            }
            if(CHECK(1)){
                if(dp[i+1][1] < dp[i][1]+ns[i]) dp[i+1][1] = dp[i][1]+ns[i];
                if(dp[i+1][2] < dp[i][1]) dp[i+1][2] = dp[i][1];
                if(dp[i+1][3] < dp[i][1]+ns[i]) dp[i+1][3] = dp[i][1]+ns[i];
                if(dp[i+1][4] < dp[i][1]+ns[i]) dp[i+1][4] = dp[i][1]+ns[i];
            }
            if(CHECK(2)){
                if(dp[i+1][2] < dp[i][2]) dp[i+1][2] = dp[i][2];
                if(dp[i+1][3] < dp[i][2]+ns[i]) dp[i+1][3] = dp[i][2]+ns[i];
                if(dp[i+1][4] < dp[i][2]+ns[i]) dp[i+1][4] = dp[i][2]+ns[i];
            }
            if(CHECK(3)){
                if(dp[i+1][3] < dp[i][3]+ns[i]) dp[i+1][3] = dp[i][3]+ns[i];
                if(dp[i+1][4] < dp[i][3]+ns[i]) dp[i+1][4] = dp[i][3]+ns[i];
            }
            if(CHECK(4)){
                if(dp[i+1][4] < dp[i][4]) dp[i+1][4] = dp[i][4];
            }
        }
        printf("%d\n",dp[n][4]);
    }

    return 0;
}