题目链接
https://nanti.jisuanke.com/t/19975
题意
Alice 和 Bob 玩游戏 在一个4x4 的方格上 每个人 每次选择2x2的区域 将里面的四个值求和加到最后的分数当中(两个人共用一个分数)，然后逆时针翻转他们，Alice 想要分数尽量打 Bob 想要分数尽量小 两个人每次的选择 都是最优的 求最后的分数
思路
玩的次数为 2k k最大为3 数据比较小，想暴力。
我们从后面往前思考
假如我们知道这个棋盘最后一步的状况，那么这时候轮到Bob 选择区域 那么它肯定会选择 和最小的一块区域
那么这个时候 再往上走一步 到 Alice 选择的时候， Alice 肯定会选择 和最大的一块区域 那么 回溯上去 就可以了
然后 只要dfs枚举每一种情况
AC代码
#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define pb push_back #define fi first #define se second #define L(on) ((on)<<1) #define R(on) (L(on) | 1) #define mkp(a, b) make_pair(a, b) #define bug puts("***bug***"); #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define CLR(a, b) memset(a, (b), sizeof(a)); #define syn_close ios::sync_with_stdio(false); cin.tie(0); #define sp system("pause"); //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef vector <int> vi; typedef vector <ll> vll; typedef vector < vi > vvi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; inline int read() { char c = getchar(); int ans = 0, vis = 1; while (c < '0' || c > '9') { if (c == '-') vis = -vis; c = getchar(); } while (c >= '0' && c <= '9') { ans = ans * 10 + c - '0'; c = getchar(); } return ans * vis; } const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fll; const int maxn = (int)1e2 + 10; const int MAXN = (int)1e4 + 10; const ll MOD = (ll)1e9 + 7; int k; int arr[4][4]; void input() { k = read(); for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) arr[i][j] = read(); } int value(int i, int j) { return arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1]; } int select(int cur, int x, int y) { if (cur % 2) return min(x, y); return max(x, y); } int Index[2][4][2] = { 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, }; int dfs(int cur) { if (cur == 2 * k - 1) { int ans = INF; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) ans = min(ans, value(i, j)); return ans; } int ans = ((cur & 1) == 1 ? INF : 0); for (int i = 0; i < 9; i++) { int x = i / 3, y = i % 3; int f[4] = { arr[x][y], arr[x][y + 1], arr[x + 1][y], arr[x + 1][y + 1] }; for (int j = 0; j < 4; j++) arr[x + Index[0][j][0]][y + Index[0][j][1]] = f[j]; ans = select(cur, ans, value(x, y) + dfs(cur + 1)); for (int j = 0; j < 4; j++) arr[x + Index[1][j][0]][y + Index[1][j][1]] = f[j]; } return ans; } int main() { int t = read(); while (t--) { input(); printf("%d\n", dfs(0)); } }转载于:https://www.cnblogs.com/Dup4/p/9433062.html
