17南宁区域赛 I - Rake It In 【DFS】

题目链接

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("%dn", dfs(0));
}
}

最后

以上就是勤劳雪碧为你收集整理的17南宁区域赛 I - Rake It In 【DFS】的全部内容，希望文章能够帮你解决17南宁区域赛 I - Rake It In 【DFS】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。