IOICJ 82 Minions ( DP )

Problem Description:
Currently you have n minions in a row on the war field, where each minion at the i'th position shows an attack value of a[ i ]. You have another m aces yet to be summoned. You can set aces at both ends or between any two minions and / or aces. Aces shows attack value of 0, but it can double the attack value of its adjacent minions. Therefore, if a minion is surrounded by two aces, its attack value is quadrupled. You want to know the maximum sum of attack value achievable.

Constraints:
1≤T≤100
1≤n≤1000
1≤m≤n+1
0≤ai≤100000
TL: 1000 ms

Sample Input:
3
4 1
5 1 3 4
4 2
5 1 3 4
4 5
5 1 3 4

Sample Output:
20
29
52

Solution:
For each minion where it is yet to be decided whether an ace should be put behind, we are only interested in whether there is an ace directly before it.
dp[ i ][ j ][ k ] : maximum sum of attack values having considered first i minions and having put j aces already, where k indicates whether there is an ace directly before the i'th minion
See the code below for clarity in the transition.

const int MAXN = ( int ) 1e3;

int N, M;
int A[ MAXN ];

int dp[ MAXN + 1 ][ MAXN + 1 + 1 ][ 2 ];

void solve(){
  int T; cin >> T;
  for( int ti = 0; ti < T; ++ti ){
    cin >> N >> M;
    for( int i = 0; i < N; ++i ){
      cin >> A[ i ];
    }
    memset( dp, -1, sizeof( dp ) );
    dp[ 1 ][ 0 ][ 0 ] = A[ 0 ];
    dp[ 1 ][ 1 ][ 1 ] = 2 * A[ 0 ];
    for( int i = 1; i < N; ++i ){
      for( int j = 0; j <= min( N, M ); ++j ){
        for( int k = 0; k < 2; ++k ){
          if( k == 0 ){
            upmax( dp[ i + 1 ][ j ][ 0 ], dp[ i ][ j ][ 0 ] + A[ i ] ); // okanai
            if( j + 1 <= M ){
              upmax( dp[ i + 1 ][ j + 1 ][ 1 ], dp[ i ][ j ][ 0 ] + A[ i - 1 ] + 2 * A[ i ] ); // oku
            }
          } else{
            upmax( dp[ i + 1 ][ j ][ 0 ], dp[ i ][ j ][ 1 ] + A[ i ] ); // okanai
            if( j + 1 <= M ){
              upmax( dp[ i + 1 ][ j + 1 ][ 1 ], dp[ i ][ j ][ 1 ] + 2 * ( A[ i - 1 ] + A[ i ] ) );
            }
          }
        }
      }
    }
    int ans = max( dp[ N ][ M ][ 0 ], dp[ N ][ M ][ 1 ] );
    upmax( ans, dp[ N ][ M - 1 ][ 0 ] + A[ N - 1 ] );
    upmax( ans, dp[ N ][ M - 1 ][ 1 ] + 2 * A[ N - 1 ] );
    cout << ans << endl;
  }
}