你的粪坑v2

一听说这是一场正经比赛，都没人用昵称了？好吧，那就用“你”吧，请自行代入聚聚名字！

这是一道充满味道的题目。

今天举办程序设计比赛，2点30分开始，然而你睡到了2点25分，紧张的你将头发梳成大人模样，敷上一层最贵的面膜，穿着滑板鞋，以飞一般的速度奔向计算机学院准备参加程序设计竞赛！冠军是你的！

然而路上稍不留神，你不小心掉进了一个大粪坑，大粪坑是一个N*N的方格矩阵，每个方格存在着X坨粪，一开始你处在A₁₁的粪坑位，你可以选择向下移动或者向右移动，目标是逃离大粪坑到达A_NN。

此外！！敲重点！！每经过一个粪坑，你会触及粪量X（粗俗的说法叫做吃shi），而且每更改一次方向，传说中的粪皇会向你丢粪！！

粪皇是个学过二进制的优雅美男子，所以他丢粪也是相当的儒雅随和。第一次他会向你丢1坨，第二次他会向你丢2坨哦，第三次他会向你丢4坨哦！第四次他会向你丢8坨哦！第五次他会向你丢16坨哦！....，第N次他会向你丢2^N-1坨哦！嘤嘤嘤～～～～～～～

机智的你绝不会向粪皇低头！所以你拿起手中的笔记本，打开Codeblocks，写下#include<bits/stdc++.h>，开始计算如何掉最少的发，吃最少的shi，冲出粪坑，到达计院，拿下冠军！

第一行是一个整数T，代表测试数据个数。

对每个测试数据第一行是一个整数N，代表粪坑大小为N*N (1 ≤ N ≤ 100) 。

接下来N行每行N个整数，代表粪坑矩阵A中每个粪坑位的粪量(1 ≤ Aij ≤ 100)。

#include<bits/stdc++.h> using namespace std; typedef long long ll; int dp[105][105][105][2],n,a[105][105],inf=0x3f3f3f3f; int dfs(int x,int y,int c,int s) { if(c>20) return inf; if(x>n||y>n) return inf; if(dp[x][y][c][s]!=inf) return dp[x][y][c][s]; if(x==n&&y==n) { return dp[x][y][c][s]=a[n][n]; } if(s==0) return dp[x][y][c][s]=a[x][y]+min(dfs(x,y+1,c,0),dfs(x+1,y,c+1,1)+(1<<c)); else return dp[x][y][c][s]=a[x][y]+min(dfs(x+1,y,c,1),dfs(x,y+1,c+1,0)+(1<<c)); } int main() { int T; scanf("%d",&T); while(T--) { memset(dp,0x3f,sizeof(dp)); scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); printf("%d\n",min(dfs(1,1,0,1),dfs(1,1,0,0))); } return 0; }

#include<bits/stdc++.h> using namespace std; typedef long long ll; int dp[105][105][105][2],n,a[105][105],inf=0x3f3f3f3f; int dfs(int x,int y,int c,int s){ if(c>20)return inf; if(x>n||y>n)return inf; if(dp[x][y][c][s]!=inf)return dp[x][y][c][s]; if(x==n&&y==n){ return dp[x][y][c][s]=a[n][n]; } if(s==0)return dp[x][y][c][s]=a[x][y]+min(dfs(x,y+1,c,0),dfs(x+1,y,c+1,1)+(1<<c)); else return dp[x][y][c][s]=a[x][y]+min(dfs(x+1,y,c,1),dfs(x,y+1,c+1,0)+(1<<c)); } int main(){ int T; scanf("%d",&T); while(T--){ memset(dp,0x3f,sizeof(dp)); scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)scanf("%d",&a[i][j]); printf("%d\n",min(dfs(1,1,0,1),dfs(1,1,0,0))); } return 0; }

详情