[AOJ] No. 0644 水ようかん (Mizuyokan)
問題
方針
最小値を固定
水ようかんを切り分けた時の長さの値は、切る箇所を任意の \( 2 \) 点選ぶことを考えると、最大でも
\[\dfrac{N(N + 1)}{2} – 1\]
あることが分かります。したがって、最小値を固定したときの、最大値を変数とみて、最大値の最小値を求めます。
動的計画法
水ようかんのピースの最小値を \( l \) と固定して動的計画法を行います。このとき、\( d_i \) を \( i \) 番目の切れ目まで調べたのピースの最大値の最小値とします。初期値は、\( d_i = 0 \) とし、それ以外は、\( d_i = \infty \) とします。また、更新後の配列は \( l \leq d_i \ ( i \neq 0 )\) を満たす必要があります。
配列の更新は、\( i \) 番目の切れ目から先頭に向かって連結させていきます。このときのピースの長さを \( t \) とします。\( 0 \leq j \leq i \) となる \( j \) について、\( l \leq t \) のとき、
\[d_{i + 1} = \min(d_{i+1}, \max(d_j, t))\]
となります。\( j \) について、\( i \) から \( 0 \) へと更新していきます。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int N; int L[50]{}; int a[51]{}; // 累積和 int ans = INT32_MAX; int dp[51]{}; void solve(int l) { fill(dp, dp + 51, 100000000); dp[0] = 0; for (int i = 0; i < N; i++) { int t = 0; for (int j = i; j >= 0; j--) { t += L[j]; // 水ようかん全てを連結したものは除外する if(i == N - 1 && j == 0) continue; if (t >= l) { dp[i + 1] = min(dp[i + 1], max(dp[j], t)); } } } ans = min(ans, dp[N] - l); } int main() { cin >> N; for (int i = 0; i < N; i++) { cin >> L[i]; } for (int i = 0; i < N; i++) { a[i + 1] += a[i] + L[i]; } set<int> s; for (int i = 0; i < N; i++) { for (int j = i + 1; j <= N; j++) { s.insert(a[j] - a[i]); } } // 水ようかんの全体の長さは除外 s.erase(*s.rbegin()); for (int i : s) { solve(i); } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません