第９回日本情報オリンピック 本選 「お菓子の分割」

ヤバ問
解説は後ほど

#include <cstdio>
#include <algorithm>

using namespace std;

const int INF = 10000000;

int n,t[10003];
int dp[2][5101][2];

int main(){
  
  scanf("%d",&n);
  
  for(int i = 0;i < n-1;i++){
    scanf("%d",&t[i]);
  }
  
  for(int i = 0;i < 2;i++){
    for(int j = 0;j < 5100;j++){
      dp[i][j][0] = INF;
      dp[i][j][1] = INF;
    }
  }
  
  dp[0][0][0] = 0;
  for(int i = 0;i < n;i++){
    int m = min(5010,i);
    for(int j = 0;j <= m;j++){
      dp[(i+1)&1][j+1][0]=min(dp[i&1][j][0],dp[i&1][j][1]+t[i]);
			dp[(i+1)&1][j][1]=min(dp[i&1][j][1],dp[i&1][j][0]+t[i]);
		}
		dp[i&1][0][0]=INF;
	}
	printf("%d\n",dp[n%2][n/2][0]);
	return 0;
}