UnKoder #02 Animal Party
最初もっと高速なアルゴリズムにするつもりだったけど,なんかWAが出るので方針を変えた。
問題:Programming Problems and Competitions :: HackerRank
解法:メモ化再帰を使う。問題の性質上,パーティーに招待される動物は
イヌ->ネコ->イヌ->ネコ->...
ネコ->イヌ->ネコ->イヌ->...
のどちらかになるので,最初にイヌになるかネコになるかを決めて,その後は「このイヌ/ネコの区間でどれくらい時間を使うか」を決めて,次の時間はネコ/イヌでどれくらい時間を使うか,...というように決めていく。
以下ソースコード
const int MAXN = 64; int a[MAXN], b[MAXN], c[MAXN], d[MAXN]; int dp[111][2]; int N, M; int dfs(int t, int mode) { int& ret = dp[t][mode]; if (ret >= 0) return ret; ret = 0; if (mode == 0) { for (int T = t+1; T <= 100; T++) { int num = 0; for (int i = 0; i < N; i++) { if (t <= a[i] && b[i] <= T) num++; } ret = max(ret, num+dfs(T, 1)); } } else { for (int T = t+1; T <= 100; T++) { int num = 0; for (int i = 0; i < M; i++) { if (t <= c[i] && d[i] <= T) num++; } ret = max(ret, num+dfs(T, 0)); } } return ret; } int main() { cin >> N; for (int i = 0; i < N; i++) { cin >> a[i] >> b[i]; } cin >> M; for (int i = 0; i < M; i++) { cin >> c[i] >> d[i]; } memset(dp, -1, sizeof(dp)); cout << max(dfs(0, 0), dfs(0, 1)) << endl; }
すぎむさん良い問題出すよなぁ。すごい。