题解：P17219 [ICPC 2017 Nanning R] Rake It In

c2024008 · 2026-08-09 18:44:05 · 题解

P17219 [ICPC 2017 Nanning R] Rake It In

题目大意

对于 4 \times 4 的矩阵，两人交替取 2 \times 2 矩阵里的数，答案累加并逆时针翻转矩阵，一个希望结果最大，一个希望结果最小。

算法分析

使用深搜，类似于 Minimax 算法，以选取不同矩阵作为不同决策。在决策树上，按层的奇偶性分别为 Alice 和 Bob，往下深搜 2k 层，对于 Alice 层，每次返回回溯时每种决策答案的最大值；对于 Bob 层返回每种决策的最小值。关于矩阵翻转，按题目要求模拟即可。由于一块 4 \times 4 的矩阵仅包含 9 个 2 \times 2 的矩阵，所以总复杂度 O(9^{2k})。

代码

#include<iostream>
using namespace std;
const int N=15;
int a[N][N],k;
int dfs(int res,int dep){
    int ret=(dep&1)?0:1e9;//初始化
    if(dep==k*2+1) return res;//遍历到叶子
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++){
            int a1=a[i][j],a2=a[i][j+1],a3=a[i+1][j],a4=a[i+1][j+1];
            a[i][j]=a2,a[i][j+1]=a4,a[i+1][j]=a1,a[i+1][j+1]=a3;//矩阵翻转
            if(dep&1) ret=max(dfs(a1+a2+a3+a4+res,dep+1),ret);//Alice 层记录每种决策最大值
            else ret=min(dfs(a1+a2+a3+a4+res,dep+1),ret);//Bob层 记录每种决策最小值
            a[i][j]=a1,a[i][j+1]=a2,a[i+1][j]=a3,a[i+1][j+1]=a4;//矩阵恢复
        }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        cin>>k;
        for(int i=1;i<=4;i++)
            for(int j=1;j<=4;j++)
                cin>>a[i][j];
        cout<<dfs(0,1)<<'\n';
    }
    return 0;
}