AOJ0550 お菓子の分割

解法

DPる。但し普通に配列をとると逝ったので、やめよう(戒め)偶奇で分ける
dp[今の位置][A][Aの個数+1] = min(dp[前の位置][A][Aの個数],dp[前の位置][B][Aの個数] + data[今]);
dp[今の位置][B][Aの個数] = min(dp[前の位置][B][Aの個数],dp[前の位置][A][Aの個数] + data[今]);
で幸せになれた(切実)

ソース

#include<iostream>
#include<algorithm>
using namespace std;
#define INF ( 1 << 30 )
int dp[2][2][5001],data[9999];
int main(){
  int n;
  cin >> n;
  fill_n(**dp,2*2*5001,INF);
  dp[0][0][0] = 0;
  for(int i = 1 ; i < n ; i++ ){
    cin >> data[i];
  }
  for(int i = 0 ; i < n ; i++ ){
    for(int j = 0 ; j <= min(n/2,i) ; j++ ){
      dp[(i+1)&1][0][j+1] = min(dp[i&1][0][j],dp[i&1][1][j]+data[i]);
      dp[(i+1)&1][1][j] = min(dp[i&1][1][j],dp[i&1][0][j]+data[i]);
    }
    dp[(i+1)&1][0][0] = INF;
  }
  cout << min(dp[(n/2)%2][0][n/2],dp[(n/2)%2][1][n/2]) << endl;
}