dede網站地圖html文件,免費ppt模板素材網站有哪些,買布自己做網站衣服的,上海網站建設公司招聘方格取數(shù)這道題我首先想到用二維數(shù)組#xff0c;二維的思路偏向貪心算法#xff0c;即定義dp[ i ][ j ]為走到點[ i , j ]時的最佳選項#xff0c;此時保證第一遍走的時候為最佳答案#xff0c;第二遍走時為去掉第一遍走過的點時的最佳答案#xff0c;保證兩遍都是分別的最…方格取數(shù)這道題我首先想到用二維數(shù)組二維的思路偏向貪心算法即定義dp[ i ][ j ]為走到點[ i , j ]時的最佳選項此時保證第一遍走的時候為最佳答案第二遍走時為去掉第一遍走過的點時的最佳答案保證兩遍都是分別的最佳答案但非整體的最佳答案……也就是說由于第一遍是只走當前最優(yōu)的容易導致第二遍走時取不到更好的值有只能向下或向右走的限制。然后會發(fā)現(xiàn)我們無法全部走完也正符合貪心策略“只注重眼前的利益”因此此題使用二維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)//第一遍的最優(yōu)解 { 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)//第二遍的最優(yōu)解 { 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; }因此我搜題解學習了動態(tài)規(guī)劃的dp這道題應該應用4維dp。狀態(tài)定義一個四維數(shù)組 ff[i][j][k][l]表示第一次走到第 i 行第 j 列第二次到達第 k 行第 l 列能獲得的最大值。狀態(tài)轉移方程我們要考慮以下四種情況第一次從左邊過來第二次從左邊過來第一次從左邊過來第二次從上邊過來第一次從上邊過來第二次從左邊過來第一次從上邊過來第二次從上邊過來那么我們就要取這四種情況的最大值了即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; }矩陣取數(shù)游戲/求n行最大得分和每一行取數(shù)又不會影響到其他行那么只要確保每一行得分最大管好自家孩子就行了。這個在動規(guī)中叫最優(yōu)子結構每次取數(shù)是在邊緣取那么每次取數(shù)完剩下來的元素一定是在一個完整的一個區(qū)間中又是求最優(yōu)解區(qū)間DP應運而生。首先明確每行怎么取是沒關聯(lián)的所以可以看成 n 行每行跑一次區(qū)間 dp。對于每行設 fl,r? 表示取區(qū)間 l 到 r 的最大值這明顯從大區(qū)間向小區(qū)間轉移但這里說一下從小區(qū)間向大區(qū)間轉移。對于一個區(qū)間它乘的 2i 的這個 i 是第 i 次取數(shù)就應等于區(qū)間長度一個長度為 len 的區(qū)間從 len?1 轉移得到所以每次轉移乘 2 就可以解決答案乘 2i 的問題。這里要好好體會。記 ai? 表示這一行的第 i 個數(shù)對于區(qū)間 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; }