【AtCoder】ゲーム
AtCoderさんの問題
B: ゲーム - Typical DP Contest | AtCoder
参考書
難しさ(初心者目線)
・考え方****
・実装***
・面白さ****
問題概要
・すぬけくんとすめけくんがゲームを行う.
・ゲームのルールについて
・A,B2つの山がある
・山とは数字が書かれたブロックが1個ずつ積み重なったものを言う
・2人は交互にAかBの山からブロックを取る
・ブロックの数値の合計値が大きいほうが勝ち
・二人とも最善を尽くした時のすぬけくんの点数を求めよ
考え方
深さ優先全探索を再帰関数dfsを用いて行う方法について
すぬけくんのポイントを返り値とする
お互いベストを尽くすので
すぬけくんのターンはdfsが大きくなるように
すめけくんのターンはdfsが小さくなるように選んでいく(下図)
A B
1 6
5 9
上の山の場合す抜けくんはまずは1か6を取ることができる
メモ化再帰をしないとTLE
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) //方針 //深さ優先全探索+メモ化再帰で //すぬけくんのポイント=dfs(Aを何個使ったか、Bを何個使ったか、どっちのターンか) //すぬけくんのターンなら得られるポイントがmaxになるようにしたい //すめけくんはすぬけくんのポイントがminになるようにしたい int A, B; int a[1001], b[1001]; //メモ化 int dp[1001][1001][2]; //who=1がすぬけ、0がすめけ int dfs(int ai, int bi, int who){ if(dp[ai][bi][who]!=-1) return dp[ai][bi][who]; if(ai==A && bi==B) return 0; int ret = 0; //すぬけくんターン if(who==1){ int rettmp1 = 0; int rettmp2 = 0; if(ai<A) rettmp1 = dfs(ai+1, bi, who^1) + a[ai+1]; if(bi<B) rettmp2 = dfs(ai, bi+1, who^1) + b[bi+1]; ret += max(rettmp1, rettmp2); } //すめけくんターン else{ int rettmp1 = 999999999; int rettmp2 = 999999999; if(ai<A) rettmp1 = dfs(ai+1, bi, who^1); if(bi<B) rettmp2 = dfs(ai, bi+1, who^1); ret += min(rettmp1, rettmp2); } return dp[ai][bi][who] = ret; } int main(){ //入力 cin >> A >> B; FOR(i, 1, A+1) cin >> a[i]; FOR(i, 1, B+1) cin >> b[i]; //初期化 FOR(i, 0, 1001) FOR(j, 0, 1001) FOR(k, 0, 2) dp[i][j][k] = -1; cout << dfs(0, 0, 1) << endl; }