NC25186. 小帆帆走迷宫
描述
小帆帆被困在一个 NxN 的方格矩阵迷宫，每个格子中都有一个整数 A[i][j]。小帆帆从迷宫起点（左上角）格子 A[1][1]开始走，每一步可以向右或向下移动，目标是移动到迷宫的出口右下角 A[N][N]。
小帆帆需要支付的费用包括路径中经过的所有格子中的整数之和，以及改变移动方向需要支付的费用。
小帆帆第一次改变方向的费用是 1，第二次的费用是 2，第三次的费用是
4，…… 第 K 次的费用是2𝑘−1。
请你帮小帆帆算出要离开迷宫的最小花费。输入描述
第一行一个整数T，代表测试数据组数。
每一组第一行一个整数N。 (1 ≤ N ≤ 100)
以下N行每行N个整数，代表矩阵A。 (1 ≤ A[i][j] ≤ 100)
输出描述
从起点到终点路径的最小花费。
示例1
输入:
2 1 10 3 1 3 5 1 1 2 5 1 1
输出:
10 9
C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 2808K, 提交时间: 2019-09-10 15:54:19
#include<bits/stdc++.h>
using namespace std;
int dp[101][101][30][2],a[101][101];
int w[30];
int main()
{
int T,n;
w[0]=1;
for(int i=1;i<=20;i++)
w[i]=w[i-1]*2;
cin>>T;
while(T--)
{
cin>>n;
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dp[1][1][0][1]=dp[1][1][0][0]=a[1][1];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
for(int c=0;c<=20;c++)
{
dp[i][j][c][0]=min(dp[i][j][c][0],dp[i][j-1][c][0]+a[i][j]);
dp[i][j][c+1][0]=min(dp[i][j][c+1][0],dp[i][j-1][c][1]+a[i][j]+w[c]);
}
for(int c=0;c<=20;c++)
{
dp[i][j][c][1]=min(dp[i][j][c][1],dp[i-1][j][c][1]+a[i][j]);
dp[i][j][c+1][1]=min(dp[i][j][c+1][1],dp[i-1][j][c][0]+a[i][j]+w[c]);
}
}
int ans=0x3f3f3f;
for(int i=0;i<=20;i++)
ans=min(min(dp[n][n][i][0],dp[n][n][i][1]),ans);
cout<<ans<<endl;
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 3276K, 提交时间: 2019-04-22 15:57:16
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int f[110][110][30][2],n,t,a[110][110];
void dp()
{
int i,j,k;
memset(f,inf,sizeof(f));
f[0][1][0][0]=f[1][0][0][1]=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=0;k<=20;k++)
{
f[i][j][k][0]=min(f[i][j][k][0],f[i-1][j][k][0]+a[i][j]);
f[i][j][k][1]=min(f[i][j][k][1],f[i][j-1][k][1]+a[i][j]);
if(k>=1)
{
f[i][j][k][0]=min(f[i][j][k][0],f[i-1][j][k-1][1]+a[i][j]+(1<<(k-1)));
f[i][j][k][1]=min(f[i][j][k][1],f[i][j-1][k-1][0]+a[i][j]+(1<<(k-1)));
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
cin>>n;int i,j,min1=1e9;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) cin>>a[i][j];
dp();
for(i=0;i<=20;i++)
{
min1=min(min1,f[n][n][i][0]);
min1=min(min1,f[n][n][i][1]);
}
cout<<min1<<endl;
}
}