mayoko’s diary

プロコンとかいろいろ。

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;
}