アルゴリズム イントロダクション 章末問題 15-2 プリンタによる浄書

入力文章は文字数が l1, l2, ..., ln の n 個の単語の列です.
この文章を 1 行最大 M 文字の行に印字したいとします.
同じ行の単語と単語の間には空白が一つ入ります.
最終行を除く, 各行の行端の空白の三乗和を最小にするように印字するアルゴリズムを考えよ,
という問題です.

問題文にもあるように動的計画法にて解くことを考えます.
ここでは行端の空白の三乗和の最小値を出力するプログラムを作成しました.
S[i,j] を単語 i から単語 j を使ったときの行端の空白の三乗和であるとします.
求めるものは, S[1,n] になります. 単語 i から j の長さの和を sumw(i,j)とすると,
S[i,j] は, M-j+i-sumw(i,j)の三乗(1), S[i,k]+S[k+1,j], i <= k <= j-1 のうちの最小値となります.
(1) では, 単語 i から j が一行に収まらない場合は, 負の値になるのでこの場合は,
この値を最小値とすることはできませんので無視します. また, 負ではない場合で, j == n の場合,
これは最終行なので 0 となり, 自動的に最小値になります.
この計算は, 下のプログラムの cost 関数にて行っています. 単語 i から j が収まらない場合は
十分に大きな値を返しておけばよいので, INT_MAX を返しています

S[i,i] 1 <= i < n については, (1) の式にて計算できます.S[n,n] は最終行なので 0 になります.

for の 3 重ループでそれぞれの添字はたかだか n 個の値をとるので実行時間は O(n^3) になります.

#include <limits.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

int S[1001][1001];
int M;
int n;

int cost(const std::vector<int>& wlv, int first, int last)
{
  int c = M-last+first-std::accumulate(wlv.begin()+first, wlv.begin()+last+1, 0);
  if(c < 0) {
    return INT_MAX;
  } else if(last == n) {
    return 0;
  } else {
    return c*c*c;
  }
}

int main() {
  int C;
  std::cin >> C;
  for(int c = 1; c <= C; ++c) {
    std::cin >> M;
    std::cin >> n;
    std::vector<int> wlv(n+1, 0);
    for(int i = 1; i <= n; ++i) {
      std::cin >> wlv[i];
    }
    
    memset(S, 0, sizeof(S));
    for(int i = 1; i < n; ++i) {
      S[i][i] = cost(wlv, i, i);
    }
    for(int l = 2; l <= n; ++l) {
      for(int i = 1; i <= n-l+1; ++i) {
	int j = i+l-1;
	int c = cost(wlv, i, j);
	if(c > 0) {
	  for(int k = i; k <= j-1; ++k) {
	    c = std::min(c, S[i][k]+S[k+1][j]);
	  }
	}
	S[i][j] = c;
      }
    }
    std::cout << "Case #" << c << ": " << S[1][n] << std::endl;
  }
}

サンプル入力

2
10
10 3 5 9 2 3 2 2 1 4 5
6
2 3 3

サンプル出力

Case #1: 4
Case #2: 27