解いた問題のソースコードと解説など。


POJ 3390 Print Words in Lines

問題

N個の文字があり、各文字の文字数が数値として与えられる。文字は与えられた順に(間にスペースを一つ入れて)連結して出力することができ、一行あたり最大でM文字出力する事ができる。ただし文字の途中で改行してはいけない。
出力する各行には(M-行の文字数)の二乗のペナルティが加算され、これらの総和を全体のペナルティとして計算する。
全体のペナルティを最小化せよ。

やりかた

dp[i]:=(i番目の文字までを使ったときのペナルティの最小値)でDP。

更新式は
L = \sum_{j}^i len[j]としてdp[i] = \min_j(dp[j-1] + (M - L)^2)
で、プログラム上はO(MN)で計算できる。

以下ソース。

int len[10001];
int dp[10001];

int main(int argc, char **argv){
  int T, M, N;
  scanf("%d", &T);
  while(T--){
    scanf("%d %d", &M, &N);
    for(int i = 0; i < N; i++)
      scanf("%d", len + i);

    FILL(dp, INF);
    for(int i = 0; i < N; i++){
      int L = 0;
      for(int j = i; j >= 0; j--){
	L += len[j];
	if(L > M) break;
	int v = j == 0 ? 0 : dp[j - 1];
	dp[i] = min(dp[i], v + (M - L) * (M - L));
	L++; //a space between two words
      }
    }
    printf("%d\n", dp[N - 1]);
  }
  return 0;
}
罪を憎んで人は憎まずにセクシー