POJ 3390 Print Words in Lines
問題
N個の文字があり、各文字の文字数が数値として与えられる。文字は与えられた順に(間にスペースを一つ入れて)連結して出力することができ、一行あたり最大でM文字出力する事ができる。ただし文字の途中で改行してはいけない。
出力する各行には(M-行の文字数)の二乗のペナルティが加算され、これらの総和を全体のペナルティとして計算する。
全体のペナルティを最小化せよ。
やりかた
dp[i]:=(i番目の文字までを使ったときのペナルティの最小値)でDP。
更新式は
]として
で、プログラム上は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; }
Get up! 明日のSUPER ST@R!