Dividing Snacks (お菓子の分割)

JOI非公式難易度表7の問題。結構、険しかった。
問題は読んで、どうぞ。
Dividing Snacks | Aizu Online Judge
DPであろうとは思ったけど、どんなふうにするか検討がつかない。
でもしばらく考えるとN個の長さ1mmのお菓子をAとBの二つのグループに分けていくと考えればよさそうということに気づく。
dp[N][Aに選んだ数][AかBか]でいけそう。
しかし制約が2<=N<=10000であるためMLE（険しい）
またしばらく考えてdp[i+1][...][...]がdp[i][...][...]によって決まるためdp配列を使いまわせることに気づく(勝った)

#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define FI first
#define SE second
using namespace std;
typedef pair<int,int> pii;
static const int inf = 1ll<<60;
static const int MAX_N = 10000;
int N;
int a[MAX_N+5];
int dp[2][MAX_N/2+5][2];
 
signed main(){
    cin>>N;
    for(int i=1;i<N;++i)cin>>a[i];
    for(int i=0;i<2;++i)for(int j=0;j<N/2;++j)for(int k=0;k<2;++k)dp[i][j][k]=inf;
    dp[0][0][0]=0;
    for(int i=0;i<N;++i){
        for(int j=0;j<N/2;++j){
            dp[(i+1)%2][j+1][0]=min(dp[i%2][j][0],dp[i%2][j][1]+a[i+1]);
            dp[(i+1)%2][j][1]=min(dp[i%2][j][0]+a[i+1],dp[i%2][j][1]);
        }
        for(int j=0;j<N/2;++j)dp[i%2][j][0]=dp[i%2][j][1]=inf;
    }
    cout<<min(dp[N%2][N/2][0],dp[N%2][N/2][0])<<endl;
}