题目链接：https://nanti.jisuanke.com/t/A1538
题意：给一个4*4的方阵，k个回合，a和b轮流选一个2*2的矩阵和，a要使和最大，b要使和最小，选完后2*2矩阵要逆时针旋转九十度，a先选，然后求最合理的答案。
思路：因为方阵只有4*4，所以暴力dfs。
#include<cstring> #include<algorithm> #include<vector> #include<map> #include<queue> #include<cstdio> #include<stack> #include<cmath> #include<iostream> #define ll long long #define lowbit(x) x&(-x) #define maxn 1050000 #define inf 0x3f3f3f3f using namespace std; int mp[5][5]; int k; void shun(int x,int y) { 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; } void ni(int x,int y) { 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; } int fun(int x,int y) { return mp[x][y]+mp[x+1][y]+mp[x+1][y+1]+mp[x][y+1]; } int dfs(int dep) { if(dep==2*k) { int mi=inf; for(int i=1;i<=3;i++) { for(int j=1;j<=3;j++) { mi=min(mi,fun(i,j)); } } return mi; } if(dep%2==1) { int ma=0; for(int i=1;i<=3;i++) { for(int j=1;j<=3;j++) { ni(i,j); int ans=fun(i,j)+dfs(dep+1); ma=max(ma,ans); shun(i,j); } } return ma; } else { int mi=inf; for(int i=1;i<=3;i++) { for(int j=1;j<=3;j++) { ni(i,j); int ans=fun(i,j)+dfs(dep+1); mi=min(mi,ans); shun(i,j); } } return mi; } } 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]); } } int ans=dfs(1); printf("%d\n",ans); } }