参考了一下《训练指南》，发现我比赛的时候写的是弱化版的Alpha-Beta剪枝……以下为正版
我们显然可以贪心地按照当前一步的获利，优先搜索更利于当前游戏者的后继节点。这样进行节点排序之后，Alpha-Beta剪枝的效率可以大大提高。

另外，本题卡常数……标程跑了1700+ms，时间限制只开2s……我用了 std::pair 然后直接卡超时了，手写 pair 才过……

附代码（C++11）：

#include <bits/stdc++.h>
using namespace std;

template<typename T1, typename T2>
struct P {
    T1 fst; T2 snd;
    P() {}
    P(T1 a, T2 b) {
        fst = a, snd = b;
    }
    bool operator<(const P<T1, T2> &rhs) const {
        return fst == rhs.fst ? snd < rhs.snd : fst < rhs.fst;
    }
    bool operator>(const P<T1, T2> &rhs) const {
        return fst == rhs.fst ? snd > rhs.snd : fst > rhs.fst;
    }
};

template<typename T1, typename T2>
P<T1, T2> MP(T1 fst, T2 snd) {
    return P<T1, T2>(fst, snd);
}

typedef P<int, P<int, int> > info;

struct State {
    int step, score, Board[4][4];
    inline void rotate_rev(int i, int j) {
        swap(Board[i][j+1], Board[i+1][j+1]);
        swap(Board[i+1][j], Board[i+1][j+1]);
        swap(Board[i+1][j], Board[i][j]);
    }
    inline void rotate_clk(int i, int j) {
        swap(Board[i+1][j], Board[i][j]);
        swap(Board[i+1][j], Board[i+1][j+1]);
        swap(Board[i][j+1], Board[i+1][j+1]);
    }
};

const int INF = 0x3f3f3f3f;

constexpr int H(State &x, int i, int j) {
    return x.Board[i][j] + x.Board[i][j+1]
         + x.Board[i+1][j] + x.Board[i+1][j+1];
}

int AlphaBeta(State &S, int player, int alpha, int beta) {
    if(S.step == 0) return S.score;
    
    int sz = 0; info vec[9];
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            vec[sz++] = MP(H(S, i, j), MP(i, j));
    if(!player)
        sort(vec, vec+9, greater<info>());
    else
        sort(vec, vec+9, less<info>());
    
    for(info &p : vec) {
        S.rotate_rev(p.snd.fst, p.snd.snd);
        S.step--; S.score += H(S, p.snd.fst, p.snd.snd);
        
        int v = AlphaBeta(S, player^1, alpha, beta);
        if(!player) alpha = max(alpha, v);
        else beta = min(beta, v);
        
        S.rotate_clk(p.snd.fst, p.snd.snd);
        S.step++; S.score -= H(S, p.snd.fst, p.snd.snd);
        if(alpha >= beta) break;
    }
    return !player ? alpha : beta;
}

int T, k; State S;

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &k); S.step = 2*k; S.score = 0;
        for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
                scanf("%d", &S.Board[i][j]);
        printf("%d\n", AlphaBeta(S, 0, -INF, INF));
    }
    return 0;
}

对于这种最大最小化的双人游戏，最基本的思路是分支定界的搜索，也就是alpha-beta剪枝，这就可以得到60分。

满分做法还需要用到启发式搜索，这里的启发式函数很容易找到：优先选取下一步获利最大（最小）的方案。

下面的代码供参考。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXK=12;
const int MAXV=10;
const int MAXN=4;

const int INF=MAXK*MAXV*4;

int n,k,sum;
int a[MAXN][MAXN];

void RotL(int i,int j){
    int tmp=a[i][j];
    a[i][j]=a[i][j+1];
    a[i][j+1]=a[i+1][j+1];
    a[i+1][j+1]=a[i+1][j];
    a[i+1][j]=tmp;
    sum+=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
}

void RotR(int i,int j){
    int tmp=a[i][j];
    a[i][j]=a[i+1][j];
    a[i+1][j]=a[i+1][j+1];
    a[i+1][j+1]=a[i][j+1];
    a[i][j+1]=tmp;
    sum-=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
}

int pro_max(int height,int downbound,int upbound);
int pro_min(int height,int downbound,int upbound);

int pro_max(int height,int downbound,int upbound){
    if(height==k)
        return sum;
    pair<int,int> heuristic_order[9];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++){
            int sum2times2=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
            heuristic_order[i*3+j]=make_pair(sum2times2,i*3+j);
        }
    sort(heuristic_order,heuristic_order+9);
    for(int t=8;t>=0;t--){
        int i=heuristic_order[t].second/3;
        int j=heuristic_order[t].second%3;
        RotL(i,j);
        int val=pro_min(height+1,downbound,upbound);
        RotR(i,j);
        if(val>=upbound)
            return upbound;
        if(val>downbound)
            downbound=val;
    }
    return downbound;
}

int pro_min(int height,int downbound,int upbound){
    if(height==k)
        return sum;
    pair<int,int> heuristic_order[9];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++){
            int sum2times2=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
            heuristic_order[i*3+j]=make_pair(sum2times2,i*3+j);
        }
    sort(heuristic_order,heuristic_order+9);
    for(int t=0;t<=8;t++){
        int i=heuristic_order[t].second/3;
        int j=heuristic_order[t].second%3;
        RotL(i,j);
        int val=pro_max(height+1,downbound,upbound);
        RotR(i,j);
        if(val<=downbound)
            return downbound;
        if(val<upbound)
            upbound=val;
    }
    return upbound;
}

int main(){
    int test;
    cin>>test;
    for(int cas=1;cas<=test;cas++){
        cin>>k;
        k*=2;
        n=4;
        for(int x=0;x<n;x++)
            for(int y=0;y<n;y++)
                cin>>a[x][y];
        sum=0;
        int ans=pro_max(0,0,INF);
        cout<<ans<<"\n";
    }
} 

NegaMax+AlphaBeta剪枝+启发式：优先选取最大（最小）的方案
总用时约14s

#include<bits/stdc++.h>
using namespace std;

const int INF=100000000;

int k,T,sum;
int a[5][5];

struct node
{
    int i,j,val;
    bool operator < (node& x)
    {
        return val<x.val;
    }
};

void Rot_anticlock(int i,int j)
{
    int t=a[i][j];
    a[i][j]=a[i][j+1];
    a[i][j+1]=a[i+1][j+1];
    a[i+1][j+1]=a[i+1][j];
    a[i+1][j]=t;
}

void Rot_clock(int i,int j)
{
    int t=a[i][j];
    a[i][j]=a[i+1][j];
    a[i+1][j]=a[i+1][j+1];
    a[i+1][j+1]=a[i][j+1];
    a[i][j+1]=t;
}

void input()
{
    cin >>k;
    for(int i=1; i<=4; i++)
    {
        for(int j=1; j<=4; j++)
        {
            cin >>a[i][j];
        }
    }
}

int NegaMax(int dep,int alpha,int beta)
{
    if(dep==(k<<1)) return sum;

    int t,ins=0;
    node arr[10];
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            ins++;
            t=a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1];
            arr[ins].i=i;
            arr[ins].j=j;
            arr[ins].val=t;
        }
    }
    sort(arr+1,arr+10);

    if(dep&1) ins=1;
    else ins=9;
    for(int i=1;i<=9;i++)
    {
        Rot_anticlock(arr[ins].i,arr[ins].j);
        sum+=arr[ins].val;
        t=-NegaMax(dep+1,-beta,-alpha);
        Rot_clock(arr[ins].i,arr[ins].j);
        sum-=arr[ins].val;
        if(t>=beta)
        {
            return beta;
        }
        alpha=max(alpha,t);

        if(dep&1) ins++;
        else ins--;
    }
    return alpha;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>T;
    while(T--)
    {
        input();

        sum=0;
        cout <<NegaMax(0,-INF,INF)<<endl;
    }

    return 0;
}