AOJ 2312 Magical Girl Sayaka-chan
解法
サンプル 1 みたいな感じで, K は 山のような形(小 -> 中 -> 大 -> 中 -> 小) になっているのが良さそうな気がします。実際にこれは正しいです。雰囲気証明すると, a <= b <= c であるような a, b, c について, a c b と並べると a b c と並べるのに比べて この後が不利(この後 c <= x を満たすような x を並べていくので) であり, また
[(Sa+...+Sb)/L] + [(Sb+...+Sc)/L] <= [(Sa+...+Sc)/L] + [(Sb+...+Sc)/L]
が成り立つからです。
ということで, 円環を K[N-1] から小さいものを両側にうまいこと並べていくことを考えます。
dp[lp][rp] = (円環の左端が lp, 右端が rp である時のコストの最小値) とすると, O(N^2) の dp ができます。
const int MAXN = 2222; const int MAXM = 100100; const ll INF = 1ll<<60; int K[MAXN], S[MAXM]; ll sum[MAXM]; ll dp[MAXN][MAXN]; int N, M, L; ll dfs(int lp, int rp) { ll& ret = dp[lp][rp]; if (ret >= 0) return ret; if (min(lp, rp) == 0) { int maxi = max(lp, rp), mini = min(lp, rp); return ret = (sum[K[maxi]+1] - sum[K[mini]]) / L; } int now = min(lp, rp)-1; ret = (sum[K[lp]+1]-sum[K[now]])/L + dfs(now, rp); ret = min(ret, (sum[K[rp]+1]-sum[K[now]])/L + dfs(lp, now)); return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M >> L; for (int i = 0; i < N; i++) { cin >> K[i]; K[i]--; } sort(K, K+N); for (int i = 0; i < M; i++) cin >> S[i]; for (int i = 0; i < M; i++) { sum[i+1] = sum[i] + S[i]; } memset(dp, -1, sizeof(dp)); cout << dfs(N-1, N-2) + (sum[K[N-1]+1]-sum[K[N-2]])/L << endl; return 0; }