0550-Dividing Snacks

問題概要

日本語なので略

解法

図のようにおかしの各場所に0か1を割り当てることを考える．

すると0と1の切り替わる場所で切断することが分かるので，
DP[いままで見た切断箇所の個数][0の個数][一つ前のマスの数値]=その最小コストのようにすることが出来る．
DP[i][j]に対する漸化式は
DP[i+1][j+1][0]=min(DP[i][j][0],DP[i][j][1]+cost[i])
DP[i+1][j][1]=min(DP[i][j][1],DP[i][j][0]+cost[i])
のようになる．初期条件はDP[0][0][0]=0．

このままではメモリが足りなくなるので，DP配列を偶奇で使い回す．

実装(C)

#include <stdio.h>
#include <string.h>
#define min(a,b) (a)>(b)?(b):(a)
int k[10000];
short dp[2][5101][2];

int main() {
	int N,i,j;
	scanf("%d",&N);
	for(i=0;i<N-1;i++)
		scanf("%d",&k[i]);
	memset(dp,0x7f,sizeof(dp));
	dp[0][0][0]=0;
	for(i=0;i<N;i++){
		int m=min(5009,i);
		for(j=0;j<=m;j++){
			dp[(i+1)&1][j+1][0]=min(dp[i&1][j][0],dp[i&1][j][1]+k[i]);
			dp[(i+1)&1][j][1]=min(dp[i&1][j][1],dp[i&1][j][0]+k[i]);
		}
		dp[i&1][0][0]=0x7f7f;
	}
	printf("%d\n",dp[N%2][N/2][0]);
	return 0;
}