企业官网建设流程全解析

做海报可以借鉴的网站,天使投资平台官网,重庆网站建开发,网站登陆怎么做方格取数这道题我首先想到用二维数组#xff0c;二维的思路偏向贪心算法#xff0c;即定义dp[ i ][ j ]为走到点[ i , j ]时的最佳选项#xff0c;此时保证第一遍走的时候为最佳答案#xff0c;第二遍走时为去掉第一遍走过的点时的最佳答案#xff0c;保证两遍都是分别的最…方格取数这道题我首先想到用二维数组二维的思路偏向贪心算法即定义dp[ i ][ j ]为走到点[ i , j ]时的最佳选项此时保证第一遍走的时候为最佳答案第二遍走时为去掉第一遍走过的点时的最佳答案保证两遍都是分别的最佳答案但非整体的最佳答案……也就是说由于第一遍是只走当前最优的容易导致第二遍走时取不到更好的值有只能向下或向右走的限制。然后会发现我们无法全部走完也正符合贪心策略“只注重眼前的利益”因此此题使用二维dp绝非正解。代码如下。二维dp#includebits/stdc.h using namespace std; const int N11; int dp1[N][N],dp2[N][N],n,o; struct point { int x; int y; int num; }poi[N*N]; void find(int k,int l)//判断第一遍走过哪些点 { if(k0l0) { return; } else { if(dp1[k][l]-dp2[k][l]dp1[k-1][l]) { dp2[k][l]0; find(k-1,l); } else if(dp1[k][l]-dp2[k][l]dp1[k][l-1]) { dp2[k][l]0; find(k,l-1); } } } int main() { scanf(%d,n); for(;;) { o; scanf(%d%d%d,poi[o].x,poi[o].y,poi[o].num); if(poi[o].xpoi[o].ypoi[o].ypoi[o].numpoi[o].num0) { break; } else { dp1[poi[o].x][poi[o].y]poi[o].num; dp2[poi[o].x][poi[o].y]poi[o].num; } } for(int i1;in;i)//第一遍的最优解 { for(int j1;jn;j) { dp1[i][j]max(dp1[i-1][j],dp1[i][j-1]); } } find(n,n); for(int i1;in;i)//第二遍的最优解 { for(int j1;jn;j) { dp2[i][j]max(dp2[i-1][j],dp2[i][j-1]); } } printf(%d,dp1[n][n]dp2[n][n]);//输出答案 return 0; }因此我搜题解学习了动态规划的dp这道题应该应用4维dp。状态定义一个四维数组 ff[i][j][k][l]表示第一次走到第 i 行第 j 列第二次到达第 k 行第 l 列能获得的最大值。状态转移方程我们要考虑以下四种情况第一次从左边过来第二次从左边过来第一次从左边过来第二次从上边过来第一次从上边过来第二次从左边过来第一次从上边过来第二次从上边过来那么我们就要取这四种情况的最大值了即f[i][j][k][l] max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1])) a[i][j] a[k][l]。但要注意的是如果 (i,j)(k,l)那么就只能加其中一个不能重复所以此时要在原来的基础上减去一个a[i][j]。3.初始化刚开始也就是到点 (1,1) 能获得的最大值即f[1][1][1][1]​0。4.答案由于我们要求第一次和第二次走到右下角的最大值所以我们的答案为 f[n][n][n][n]​。四维dp#includebits/stdc.h using namespace std; int n,x,y,z,a[12][12] {0},f[12][12][12][12];//表示第一次走到第i行第j列第二次到达第k行第l列能获得的最大值。 int main() { cin n; cin x y z ; while(x!0||y!0||z!0) { a[x][y] z; cin x y z ; } for(int i1; in; i) { for(int j1; jn; j) { for(int k1; kn; k) { for(int l1; ln; l) { f[i][j][k][l] max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1])) a[i][j] a[k][l]; if(i k j l) f[i][j][k][l] - a[i][j];//如果位置相同则减去其中一个 } } } } cout f[n][n][n][n] endl; return 0; }矩阵取数游戏/求n行最大得分和每一行取数又不会影响到其他行那么只要确保每一行得分最大管好自家孩子就行了。这个在动规中叫最优子结构每次取数是在边缘取那么每次取数完剩下来的元素一定是在一个完整的一个区间中又是求最优解区间DP应运而生。首先明确每行怎么取是没关联的所以可以看成 n 行每行跑一次区间 dp。对于每行设 fl,r​ 表示取区间 l 到 r 的最大值这明显从大区间向小区间转移但这里说一下从小区间向大区间转移。对于一个区间它乘的 2i 的这个 i 是第 i 次取数就应等于区间长度一个长度为 len 的区间从 len−1 转移得到所以每次转移乘 2 就可以解决答案乘 2i 的问题。这里要好好体会。记 ai​ 表示这一行的第 i 个数对于区间 l 到 r可以先取 al​可以先取 ar​转移是 fl,r​max(fl1,r​al​,fl,r−1​ar​)×2。答案就是 n 次 f1,m​ 之和。#include bits/stdc.h using namespace std; int n, m, a[90][90]; __int128 f[90][90], ans; void out (__int128 x) { if(x9) out(x/10); putchar(x%100); } int main () { cin n m; for (int i1; in; i) for (int j1; jm; j) cin a[i][j]; for (int i1; in; ansf[1][m], memset(f, 0, sizeof f), i) for (int len1; lenm; len) for (int l1, rllen-1; rm; l, r) f[l][r]max(f[l1][r]a[i][l], f[l][r-1]a[i][r])*2; out(ans); return 0; }