AOJ 0550 お菓子の分割

昨日の夜、解いた。漸化式むずかしい

#include <cstdio>
#include <algorithm>
using namespace std;
 
const int INF = 1<<29;
const int MAX_N = 10000;
int N;
int a[MAX_N];
int dp[2][MAX_N][2];
 
int main(){
    scanf("%d", &N);
    a[0] = 0;
    for(int i = 1; i < N; i++)
        scanf("%d", &a[i]);
    reverse(a, a + N);
    dp[1][0][0] = a[0];
    dp[1][0][1] = INF;
    for(int i = 1; i < N; i++){
        dp[1][i][0] = INF;
        dp[1][i][1] = a[0] + a[i];
    }
    for(int k = 2; k <= N / 2; k++){
        dp[k%2][k-1][0] = a[k-1];
        dp[k%2][k-1][1] = INF;
        for(int i = k; i < N; i++){
            int t = (k-1)%2;
            dp[k%2][i][0] = min(dp[t][i-1][0] - a[i-1] + a[i], dp[t][i-1][1] + a[i]);
            dp[k%2][i][1] = min(dp[k%2][i-1][0] + a[i], dp[k%2][i-1][1] - a[i-1] + a[i]);
            //printf("(%d,%d) ", dp[k%2][i][0], dp[k%2][i][1]);
        }
    }
    printf("%d\n", min(dp[(N/2)%2][N-1][0], dp[(N/2)%2][N-1][1]));
    return 0;
}