一站式网站建设费用,免费微信网站模板下载工具,谷歌搜索引擎入口,怎么制作网站教程视频动态规划方格取数垒骰子方格取数
题目描述
设有 NNN \times NNN 的方格图 (N≤9)(N \le 9)(N≤9)#xff0c;我们将其中的某些方格中填入正整数#xff0c;而其他的方格中则放入数字 000。如下图所示#xff08;见样例#xff09;:
A0 0 0 0 0 0 0 00 0 13 0 …
动态规划方格取数垒骰子方格取数
题目描述
设有 N×NN \times NN×N 的方格图 (N≤9)(N \le 9)(N≤9)我们将其中的某些方格中填入正整数而其他的方格中则放入数字 000。如下图所示见样例:
A0 0 0 0 0 0 0 00 0 13 0 0 6 0 00 0 0 0 7 0 0 00 0 0 14 0 0 0 00 21 0 0 0 4 0 00 0 15 0 0 0 0 00 14 0 0 0 0 0 00 0 0 0 0 0 0 0B某人从图的左上角的 AAA 点出发可以向下行走也可以向右走直到到达右下角的 BBB 点。在走过的路上他可以取走方格中的数取走后的方格中将变为数字 000。 此人从 AAA 点到 BBB 点共走两次试找出 222 条这样的路径使得取得的数之和为最大。
输入格式
输入的第一行为一个整数 NNN表示 N×NN \times NN×N 的方格图接下来的每行有三个整数前两个表示位置第三个数为该位置上所放的数。一行单独的 000 表示输入结束。
输出格式
只需输出一个整数表示 222 条路径上取得的最大的和。
样例 #1
样例输入 #1
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0样例输出 #1
67注意这里需要分为 i和j 是否相等如果不相等一定不在同一个格子中那就可以取两次了为什么可以优化成三维是因为如果走的次数是固定的横坐标和纵坐标的和事固定的行数列数。 注意有了步数这一实际意义大于等于0和 步数与行数之间的约束后者必须小于前者循环的嵌套顺序和行数循环终止条件要注意
#include iostream
using namespace std;
//#define int long long int
const int N10;
int a[N][N];
int dp[N][N][N][N];
int n,x,y,s;
int get_max(int u,int v,int o,int p){return max(max(u,v),max(o,p));
}
signed main(int argc, char** argv) {cinn;while(cinxys){if(!x!y!s)break;a[x][y]s;}for(int i1;in;i){for(int j1;jn;j){for(int k1;kn;k){for(int l1;ln;l){dp[i][j][k][l]get_max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])a[i][j]a[k][l];
// 两个人一步有四种结果if(ikjl)dp[i][j][k][l]-a[i][j];}}}}coutdp[n][n][n][n];return 0;
}
#include iostream
using namespace std;
//#define int long long int
const int N10;
int a[N][N];
int dp[N][N][N*2];
int n,x,y,s;
int get_max(int u,int v,int o,int p){return max(max(u,v),max(o,p));
}
signed main(int argc, char** argv) {cinn;while(cinxys){if(!x!y!s)break;a[x][y]s;}dp[1][1][0]a[1][1];//初始化for(int k1;k(n-1)*2;k){//已经走了多少步(两个人是同时走一步)for(int i1;imin(k1,n);i){for(int j1;jmin(k1,n);j){dp[i][j][k]get_max(dp[i-1][j][k-1],dp[i-1][j-1][k-1],dp[i][j][k-1],dp[i][j-1][k-1])a[i][k2-i]a[j][k2-j];
// 两个人一步有四种结果 p1向下p2向右,都向下,都向右,p1向右p2向下if(ij)dp[i][j][k]-a[i][k2-i];
// m行n列总共 m-1n-1步
// cx行,cxi,cy列 cx-1cy-1k步 cyk2-cx }}}coutdp[n][n][(n-1)*2];return 0;}
//1 1 1
//2 2 3
//2 3 4
垒骰子 爆搜
#include iostream
using namespace std;
#define int long long int
const int mod1e97;
const int N10;
int m,n,x,y;
int back[7];
bool conflict[40][40];
int dfs(int u,int cnt){if(cntn1){return 1;}int ans0;for(int down1;down6;down){//枚举骰子底部的数字if(conflict[u][down])continue;ans(ansdfs(back[down],cnt1))%mod;}
}
int quickpow(int b,int e){b%mod;int res1;while(e){if(e1)resres*b%mod;bb*b%mod;ee1;}return res;
}
signed main(int argc, char** argv) {back[1]4;back[4]1;back[2]5;back[5]2;back[3]6;back[6]3;cinnm;for(int i0;im;i){cinxy;conflict[x][y]true;conflict[y][x]true;}int res0;for(int down1;down6;down){res(resdfs(back[down],2))%mod;}resres*quickpow(4,n)%mod;coutres;return 0;} 在这种解题方式上用快速幂有些多余。分枝过多的递归当n100时几乎不能在题目规定时间内计算出来。当n100时通过累乘的方式将4一次、一次乘给ans这并不会对程序的效率造成很大影响。
