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

140 阅读 0 评论 93 点赞

我是靠谱客的博主勤劳雪碧，这篇文章主要介绍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));
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#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));
}
}