原題地址:https://nanti.jisuanke.com/t/19975

題意:Alice和Bob在玩一種名為“Rake It In”的游戲，起初有一個(gè)44的棋盤，每一格為一個(gè)1~10的整數(shù)，兩人輪流行動(dòng)，各自k次，行動(dòng)者選擇棋盤中某一個(gè)22的區(qū)域，將這四個(gè)元素求和，加到最終答案中，并將四個(gè)元素按逆時(shí)針旋轉(zhuǎn)90度，Alice先行。Alice的目標(biāo)是最大化最后的答案，Bob相反。請(qǐng)寫一個(gè)程序計(jì)算，在兩人都最聰明的情況下，最終答案為多少。

思路:直接DFS容易卡常,正解應(yīng)該是加alpha-beta 剪枝.

附上有無剪枝的區(qū)別:

#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<deque> #include<stack> #include<map> #include<set> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #define fuck(x) cout<<#x<<" = "<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 100086; const int inf = 2.1e9; const int INF = 0x3f3f3f3f; const double eps = 1e-6; int mp[5][5], ans; int k;inline void chang(int x, int y) {//旋轉(zhuǎn)ans += mp[x][y];ans += mp[x + 1][y];ans += mp[x][y + 1];ans += mp[x + 1][y + 1];int t = mp[x][y];mp[x][y] = mp[x][y + 1];mp[x][y + 1] = mp[x + 1][y + 1];mp[x + 1][y + 1] = mp[x + 1][y];mp[x + 1][y] = t; } inline void huisu(int x, int y) {//再旋轉(zhuǎn)回來ans -= mp[x][y];ans -= mp[x + 1][y];ans -= mp[x][y + 1];ans -= mp[x + 1][y + 1];int t = mp[x][y];mp[x][y] = mp[x + 1][y];mp[x + 1][y] = mp[x + 1][y + 1];mp[x + 1][y + 1] = mp[x][y + 1];mp[x][y + 1] = t; } int dfs(int t, int alpha, int beta) {if (t > 2 * k) {return ans;}for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {chang(i, j);if (t & 1) {int cnt = dfs(t + 1, alpha, beta);alpha = alpha > cnt ? alpha : cnt;huisu(i, j);} else {int cnt = dfs(t + 1, alpha, beta);beta = beta > cnt ? cnt : beta;huisu(i, j);}if (beta <= alpha) return t & 1 ? alpha : beta;//alpha-beta 剪枝}}return t & 1 ? alpha : beta; }int main() {int T;scanf("%d", &T);while (T--) {scanf("%d", &k);for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {scanf("%d", &mp[i][j]);}}ans = 0;printf("%d\n", dfs(1, -INF, INF));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2017 ICPC Naning I. Rake It In(alpha-beta剪枝)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。