SRM 316 Div1 Medium PlacingPieces
問題
直線の棒がいくつか与えられ、それらの長さはpieces[]である。この棒からいくつか選んで長さL上の板の上に、はみ出ないように、かつ区間が互いに重ならないように置いていく。棒を置いていない区間に残りの棒が1つも置けないようになったら終了とする。置かねばならない最小の棒の数を求めよ。なお棒は端点が実数でももちろんかまわない。
やりかた
すべての棒と棒の間隙および両端の空きは同じ長さにして、これらの隙間がなるべく少ない本数でなるべく短くなるようにしたい。棒をn本使用し、これらの長さの和がsumだとすれば、この長さは(L - sum) / (n + 1)になる。この長さが、使わなかった棒のうちで最も短いやつ(★)よりも小さければいい。
とりあえず棒をソートしておく。すべての棒について(★)である可能性を調べる。ある棒が(★)である場合、それより小さい棒は必ず使用していなければならないため、これらは和を取る。その上でこの棒より、大きい物について、次のbool DPを行う。
dp[l][i][j]:=(i番目まで棒を見て、このうちj本の棒を使用して、和をlとできるか)
このDPにより、ある長さをある本数で実現できるかがわかるため、ループを回して、すべてのパターンについて、間隙を計算して、(★)より間隙が小さくなるもので本数が最小となるものを求めていけばいい。(いま着目している棒以下の長さの棒はすでに使用しているため、最低限達成しなければいけないのは着目している棒の長さになる。)
以下ソース。
bool dp[1001][50][50]; using namespace std; class PlacingPieces { public: int len; int N; vector<int> p; void calc(int idx, int cnt, int sum){ dp[sum][idx][cnt] = true; for(int i = idx; i < N; i++){ for(int j = cnt; j < N; j++){ for(int l = 0; l <= len; l++){ if(!dp[l][i][j]) continue; if(l + p[i] <= len) dp[l + p[i]][i + 1][j + 1] = true; dp[l][i + 1][j] = true; } } } return; } int optimalPlacement(int L, vector <int> pieces){ sort(ALL(pieces)); N = pieces.size(); p = pieces; len = L; int ans = N; for(int i = 0; i <= N; i++){ //すべての棒について(★)かどうか調べる int sum = 0; for(int j = 0; j < i; j++) sum += pieces[j]; //着目している棒未満の棒はすべて使用する if(sum > L) continue; memset(dp, false, sizeof(dp)); calc(i, i, sum); for(int l = 0; l <= 1000; l++) for(int k = 0; k <= N; k++) if(dp[l][N][k] && L - l >= 0 && 1.0 * (L - l) / (k + 1) < pieces[i]) ans = min(ans, k); } return ans; } };
再提出したものの自力ACできた。むかしだったらできなかったと思うので嬉しい。