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; }