龙口建网站公司价格,深圳网站建设认准乐云,网页设计实训报告实训内容,网站内容管理系统建设这道题曾经是提高组的第四题#xff0c;但是毕竟书上有#xff0c;所以emmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm#xff0c;QAQ。
Description 设有N*N的方格图(N10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示#xff08;见样例#xf…这道题曾经是提高组的第四题但是毕竟书上有所以emmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmQAQ。
Description 设有N*N的方格图(N10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示见样例 某人从图的左上角的A 点出发可以向下行走也可以向右走直到到达右下角的B点。在走过的路上他可以取走方格中的数取走后的方格中将变为数字0。 此人从A点到B 点共走两次试找出2条这样的路径使得取得的数之和为最大。 Input 输入的第一行为一个整数N表示N*N的方格图接下来的每行有三个整数前两个表示位置第三个数为该位置上所放的数。一行单独的0表示输入结束。 Output 只需输出一个整数表示2条路径上取得的最大的和。 Sample Input 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 Sample Output 67 解题思路 这道题的难点就是要走两遍但是如果dp两遍的话明显不需ok所以我可以让两个同时行走在ta们走到同一个位置时要做出判断 #includecstdio
#includeiostream
using namespace std;
int a[51][51],f[51][51][51][51],x,y,sc,n;
int main()
{scanf(%d,n);x1; y1; sc1;//进入循环while (x!0 y!0 sc!0){scanf(%d%d%d,x,y,sc);a[x][y]sc;//确定方格}for (int x11;x1n;x1)//循环第一次的xfor (int y11;y1n;y1)//循环第一次的y
for (int x21;x2n;x2)//循环第二次的xfor (int y21;y2n;y2)//循环第二次的y{int tmp1max(f[x1-1][y1][x2-1][y2],f[x1][y1-1][x2][y2-1]);//情况为左左上上int tmp2max(f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2]);//情况为左上上左f[x1][y1][x2][y2]max(tmp1,tmp2)a[x1][y1];//取最大值加上当前格子的价值if (x1!x2 y1!y2) f[x1][y1][x2][y2]a[x2][y2];//如果两个没有走到同一个格子上就加第二次的价值}printf(%d,f[n][n][n][n]);//输出
}
