本文主要是介绍方格取数（局部最优解与全局最优解的思路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
##错误代码如下##
#include<iostream>
using namespace std;
int n;
int m[20][20];
int dp[20][20];
int dp2[20][20];
int f[21][11][11];
pair<int,int>state[11][11];
int maxx(int a,int b,int c,int d){return max( max(a,b) , max(c,d) );
}
int main(){cin>>n;int x,y,z;while(cin>>x>>y>>z,x||y||z)m[x][y]=z;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1])+m[i][j];if(dp[i][j]==dp[i-1][j]+m[i][j])state[i][j]={i-1,j};else state[i][j]={i,j-1};}}int i=n,j=n;while(i||j){m[i][j]=0;int x=i,y=j;i=state[x][y].first;j=state[x][y].second;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp2[i][j]=max(dp2[i-1][j],dp2[i][j-1])+m[i][j];}}cout<<dp[n][n]+dp2[n][n];}
#include<iostream>
using namespace std;
int n;
int m[20][20];
int dp[20][20][20][20];int maxx(int a,int b,int c,int d){return max( max(a,b) , max(c,d) );
}int main(){cin>>n;int x,y,z;while(cin>>x>>y>>z,x||y||z)m[x][y]=z;for(int i1=1;i1<=n;i1++){for(int j1=1;j1<=n;j1++){for(int i2=1;i2<=n;i2++){for(int j2=1;j2<=n;j2++){int &x=dp[i1][j1][i2][j2];int t=m[i1][j1];if(i1!=i2)t+=m[i2][j2];x=maxx(dp[i1][j1-1][i2][j2-1],dp[i1][j1-1][i2-1][j2],dp[i1-1][j1][i2-1][j2],dp[i1-1][j1][i2][j2-1])+t;}}}}cout<<dp[n][n][n][n];
}
#include<iostream>
using namespace std;
int n;
int m[20][20];
int dp[20][20][20][20];
int f[21][11][11];
int maxx(int a,int b,int c,int d){return max( max(a,b) , max(c,d) );
}int main(){cin>>n;int x,y,z;while(cin>>x>>y>>z,x||y||z)m[x][y]=z;for(int k=2;k<=2*n;k++){for(int i1=1;i1<=n;i1++){for(int i2=1;i2<=n;i2++){int j1=k-i1,j2=k-i2;int &x=f[k][i1][i2];int t=m[i1][j1];if(i1!=i2)t+=m[i2][j2];x=maxx(f[k-1][i1][i2],f[k-1][i1][i2-1],f[k-1][i1-1][i2],f[k-1][i1-1][i2-1])+t;}}}cout<<f[2*n][n][n];}
#include<iostream>
#include<cstring>
using namespace std;const int N = 15;int n, r, c, num;
int f[N + N][N][N], w[N][N];int main() {cin >> n;while(cin >> r >> c >> num, r || c || num) {w[r][c] = num;}//k表示其中两条路径长度的总和for(int k = 2; k <= n + n; k++) {for(int i1 = 1; i1 <= n; i1++) {for(int i2 = 1; i2 <= n; i2++) {int j1 = k - i1, j2 = k - i2;if(j1 < 1 || j1 > n || j2 < 1 || j2 > n) continue;//要走的路径int t = w[i1][j1];if(i1 != i2) t += w[i2][j2];int& x = f[k][i1][i2];x = max(x, t + f[k - 1][i1 - 1][i2 - 1]); //上一个状态的两条路径分别往下走一格x = max(x, t + f[k - 1][i1][i2 - 1]); x = max(x, t + f[k - 1][i1 - 1][i2]);x = max(x, t + f[k - 1][i1][i2]);}}}cout << f[n + n][n][n] << endl;return 0;
}作者：抽象带师
链接：https://www.acwing.com/solution/content/30705/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1.考虑状态表示的问题（降维，对每一维度的理解）
2.考虑集合划分的问题（深入了解01思想，无论是对差分还是前缀和都很有用处）
刷题强度要跟上来！！！！！
啊啊啊啊冲冲冲！！！！
这篇关于方格取数（局部最优解与全局最优解的思路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
