AOJ2129 Text Justification

問題リンク Text Justification

• 概要

N個の単語長と幅Wが指定される。単語は入力の順に並べる。このとき、1行の文字幅がWに近付くように、改行を挿入できる。単語の途中に改行を入れることはできない。以下の方法にのっとって、単語の並べ方のコストを算出するとき、コストの最小値を求めよ。sは、1行に並べた単語長とする。
コストの値は、各行に関するコストの総和である
最終行のコストは、max{0, s-w}
それ以外の行のコストは、|s-w|
0 <= N <= 10^3
0 <= W <= 10^6
単語長 <= W

• 解法

DPです。
dp[i]: 単語iを行の最後としたときの最小コスト
という表を作ります。このとき、単語iは最終行でないものとして計算します。dp[i]は、累積和を使いつつ埋めればO(N^2)で埋まります。
最後に、最終行がiの単語から始まるとして、
min { dp[i-1] + max{0, sum[n]-sum[i-1]} }
が答えになります。

• ソース

import java.util.Scanner;

//Text Justification
public class AOJ2129 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int[] a = new int[1001], sum = new int[1001], dp = new int[1001];
		int INF = (1<<30)-1;
		for(int T=1;;T++){
			int n = sc.nextInt(), w = sc.nextInt();
			if((n|w)==0)break;
			for(int i=1;i<=n;i++){
				a[i] = sc.nextInt();
				sum[i] = sum[i-1]+a[i];
				dp[i] = INF;
			}
			for(int i=1;i<=n;i++)for(int j=0;j<i;j++)dp[i] = Math.min(dp[i], dp[j]+(Math.abs(sum[i]-sum[j]-w)));
			int res = INF;
			for(int i=1;i<=n;i++)res = Math.min(res, dp[i-1]+Math.max(0, sum[n]-sum[i-1]-w));
			System.out.printf("Case %d: %d\n", T, res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2129().run();
	}
}