DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦,D: シャツの部屋

DP

https://ddcc2016-final.contest.atcoder.jp/tasks/ddcc_2016_final_d

これは本当に良問だと思います。

まずi-1回洗濯するとすると、i+k回洗濯すると破れる服は全部i回とみなせます。
Mが小さければdp[i][j]:=i回洗濯する服まで見てj日シャツを着られる方法で最小コストのもの
で簡単にできますが今回はMが破滅的にデカイので無理です。
でも感覚的にはB/Aが小さいものを使うのが良くて、実際B/Aが最小の服がm回洗濯すると破れる服ならば、他の服はm回以上使わないことが示せます。これはmodで考えるとわかります。

m<500であり、(服の持つ日数)<500なので(最小の服以外の日数の合計)<500*500となります。なので、
dp[i][j]:=i回洗濯する服まで見てj日シャツを着られる方法で最小コストのもの(上の式と全く同じ)と定義して無制限個数ナップサック問題をときます。あとは最小の服を使ってM日に達するようにした時の最小コストを求めます。これで計算量はO((maxA)^3)となり解けました。

状態から攻めるパターンのDPですね。このタイプはなかなか見ないので苦手です。さらにm回が上界なのも結構非自明で難しいとおもいます。
chokudaiさんが作問者ということで、マラソンすればこういうの得意になるのかも?

数式に走ったんですがやっぱりダメですね。DPしようという気分になるべきでした。

int N; ll M, C;
ll cost[MAX_N];
ll dp[500 * 520];

bool comp(const pl& p1, const pl& p2) {
	return p1.fst * p2.sec < p1.sec * p2.fst;
}

void solve() {
	cin >> N >> M >> C;
	rep(i, 1, 500 + 1) cost[i] = inf;
	rep(i, 0, N) {
		ll a, b;
		cin >> a >> b;
		MIN(cost[a], b);
	}
	rer(i, 500, 1) MIN(cost[i], cost[i + 1]);
	rep(i, 0, 500 * 500) dp[i] = linf;

	pl ratio = pl(inf, 0);
	dp[0] = 0;

	ll ans = linf;
	rep(i, 1, 500 + 1) {
		ll b = cost[i];
		if(comp(pl(b, i), ratio)) ratio = pl(b, i);
		if(b == inf) break;
		rep(j, 0, 500 * 500) {
			MIN(dp[j + i], dp[j] + b);
		}
		ll B = ratio.fst, A = ratio.sec;

		rep(j, 0, 500 * 500) {
			MIN(ans, C * (i - 1) + B * max(0LL, (M - j + A - 1) / A) + dp[j]);
		}
	}
	cout << ans << "\n";
}