J

思路：分析存在四维状态: f[i][j][u][v] (1<= i , j <= 100 , 0 <= u <= 1 , 1 <= v <= 15) i , j 表示第 i 行 j 列 , u 表示方向状态即是从哪个方向转到此处(题解用 0 表示竖直方向即从上往下 , 1 反之), v 表示转向了多少次，由于A[i][j] <= 100 , 可得 ans <= 100 * 100 * 2 + 2^0 = 20001 < 2^15 = 32768 , 故设 v <= 15。

然后就是状态转移,由于状态只能从上一行或上一列转移到此处,故可以进行正向遍历矩阵，正向遍历转向次数 , 状态转移方程: f[i][j][0][k] = min(f[i][j][0][k] , f[i-1][j][0][k] + g[i][j] , f[i-1][j][1][k-1] + (1 << k - 1) + g[i][j]) , f[i][j][1][k] = min(f[i][j][1][k] , f[i][j-1][1][k] + g[i][j] , f[i][j-1][0][k-1] + (1 << k - 1) + g[i][j]);最后遍历所有可以到达A[n][n]的状态 , 取min即可。

注意初始化，由于转移方程取min , 故设初值足够大 , 不需转向的即第一行和第一列的格子也可提前预处理好，具体实现看代码:

#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
int g[102][102] , f[102][102][2][20];
int MIN(int x , int y , int z) {
    return min(x , min(y , z));
}
void solve(){
    memset(f , 0x3f3f3f3f ,sizeof f);
	int n;cin >> n;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++) cin >> g[i][j];
    f[1][1][0][0] = f[1][1][1][0] = g[1][1];
    for(int i = 2;i <= n;i ++) {
        f[i][1][0][0] = f[i-1][1][0][0] + g[i][1];
        f[1][i][1][0] = f[1][i-1][1][0] + g[1][i];
    }
    for(int i = 2;i <= n;i ++) {
        for(int j = 2;j <= n;j ++) {
            for(int k = 1;k < 15;k ++) {
                if(k > i || k > j) continue;	//转向k次行数必定小于等于 i 行 , 列数同理
                f[i][j][0][k] = MIN(f[i][j][0][k] , f[i-1][j][0][k] + g[i][j] , f[i-1][j][1][k-1] + (1 << k - 1) + g[i][j]);
                f[i][j][1][k] = MIN(f[i][j][1][k] , f[i][j-1][1][k] + g[i][j] , f[i][j-1][0][k-1] + (1 << k - 1) + g[i][j]);
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for(int i = 1;i < 15;i ++) {
        ans = MIN(ans , f[n][n][1][i] , f[n][n][0][i]);
    }
    cout << ans << '\n';
}
signed main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t = 1;
    cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}