AOJ0550 Dividing Snacks

AOJ Volume5

問題リンク Dividing Snacks

  • 解法

DPです。
dp[ i ][ j ][ k ]: 左からiミリメートルまでを考えて、k個分のお菓子を得るための最小コスト。j = 0なら、場所 i を切らない場合で、j = 1なら場所 i を切ることを表す
という表を埋めて解きます。
初期値はdp[0][0][0]のみ0でその他はINFです。
dp[ i ][ 0 ][ k ]を埋めるには話は簡単で、1個手前を切ってkを得るか、切らずにkを得るかのどちらかなので、
dp[ i ][ 0 ][ k ] = min{ dp[ i-1 ][ 0 ][ k ], dp[ i-1 ][ 1 ][ k ] }
です。
dp[ i ][ 1 ][ k ]は、
dp[ i-1 ][ 0 ][ k-1 ] + a[ i-1 ] + a[ i ] : 手前に切りこみが入っていない場合、i-1とiを切るコストがかかる
dp[ i-1 ][ 1 ][ k-1 ] - a[ i-1 ] + a[ i ] : 手前に切り込みが入っている場合、手前の切り込みコストはキャンセルし、iを切るコストがかかる
これらの場合のminとなります。
便宜上、0ミリメートルとNミリメートルの箇所を切るコストを0として配列を作っておくと、プログラムに例外処理を書く必要がなくてさっぱりすると思います
また、DPのサイズはN * 2 * N/2だけ必要でメモリが足りません。更新のときに直前の情報しか使わないので、2 * 2 * N/2だけのサイズで十分です。

  • ソース
import java.util.Scanner;

//Dividing Snacks
public class AOJ0550 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), INF = 1<<29;
		int[] a = new int[n+2];
		for(int i=1;i<n;i++)a[i]=sc.nextInt();
		int[][][] dp = new int[2][2][n/2+1];
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<=n/2;k++)dp[i][j][k]=INF;
		dp[0][0][0] = 0;
		int x = 1;
		for(int i=1;i<=n;i++,x=1-x)for(int j=0;j<2;j++){
			int t = Math.min(i, n>>1);
			for(int k=0;k<=t;k++){
				dp[x][0][k] = Math.min(dp[1-x][0][k], dp[1-x][1][k]);
				if(0<k)dp[x][1][k] = Math.min(dp[1-x][0][k-1]+a[i-1]+a[i], dp[1-x][1][k-1]-a[i-1]+a[i]);
			}
		}
		System.out.println(Math.min(dp[1-x][0][n/2], dp[1-x][1][n/2]));
	}
	
	public static void main(String[] args) {
		new AOJ0550().run();
	}
}