KUPC 2019 F - カズマ王国の陥落 解説
DPについて学びになる問題だったので、メモとして残す．
考えたこと
最初考えたのは、各拠点のモンスターは、自身が攻撃できる街の中で勇者の撃退可能数が最も少ない街を貪欲的に選んでいけば、答えが求まるのではというものでしたが、これには反例があります．
反例
- 街が2つあり、それぞれの街の勇者の撃退可能数が街1は2、街2が3である
- 拠点が2つありモンスター数は3体ずつ、拠点1は街1と2の両方を攻撃可能、拠点2は街2しか攻撃できない
この場合に上記の貪欲法を適用すると、拠点1のモンスターは街1を攻めて、1ダメージを与えるが、拠点2のモンスターはダメージを与えることができない．
一方、拠点1、2のモンスターが総じて街2を攻撃した場合、3ダメージを与えることができる．
DPで解く
各拠点がどの街を攻撃するかを独立して考える貪欲法は、上記のようにうまくいかないので、以下のように漸化式を定義しDPで解きます．
漸化式
dp[i]:=街iまでで、与えられるダメージの最大
よって、dp[N]に求めたい解が格納されます．
実装
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } ll N, A[3005], M, L[3005], R[3005], B[3005]; ll dp[3005]; vector<pll> Monster[3005]; signed main() { cin >> N; for(int i = 1; i <= N; i++) cin >> A[i]; cin >> M; for(int i = 1; i <= M; i++) { cin >> L[i] >> R[i] >> B[i]; Monster[L[i]].push_back({R[i], B[i]}); } for(int pos = 1; pos <= N; pos++) { ll num = 0; for(int nowpos = pos; nowpos >= 0; nowpos--) { // nowposまでの街に与えられるダメージの総和 + nowpos+1~posの街に与えられるダメージの総和 ← これの最大値をdp[pos]に格納する chmax(dp[pos], dp[nowpos] + max(0LL, num - A[pos])); for(int j = 0; j < Monster[nowpos].size(); j++) { // (nowposがL[i]であるMonsterであるもののうち、) pos <= R[i]を満たすMonsterであるか if(Monster[nowpos][j].first >= pos) { // num ... nowposがL[i]であるMonsterの総数. つまり、nowpos ~ posを攻撃できるMonsterの攻撃の総和 num += Monster[nowpos][j].second; } } } cerr << dp[pos] << endl; } cout << dp[N] << endl; return 0; }
