方格取数【多线程dp】

本文主要是介绍方格取数【多线程dp】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

最普通版
时间优化
滚动数组空间优化

最普通版

第一次做这种题诶~

#include"bits/stdc++.h"
using namespace std;
const int maxn=11;
int a[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];//dp[i][j][k][l]表示第一条路径取到(i,j),第二条路径取到(j,k)时的最大值 
int Max(int a,int b,int c,int d)
{return max(max(a,b),max(c,d));
}
int main()
{int N;cin>>N;int x,y,v;while(cin>>x>>y>>v&&x)a[x][y]=v;for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)for(int k=1;k<=N;k++)for(int l=1;l<=N;l++){dp[i][j][k][l]=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]);dp[i][j][k][l]+=a[i][j];if(i==k&&j==l)continue;//如果两次选的是同一个点，那么就只加一次dp[i][j][k][l]+=a[k][l];}cout<<dp[N][N][N][N]<<endl;
}

时间优化

#include"bits/stdc++.h"
using namespace std;
const int maxn=11;
int a[maxn][maxn];
int dp[maxn<<1][maxn][maxn];//dp[k][i1][i2]走了k步第一次路径到了第i1行,第二次路径到了第i2行，然后纵坐标阔以用步数相减来计算 
int Max(int a,int b,int c,int d)
{return max(max(a,b),max(c,d));
}
int main()
{int N;cin>>N;int x,y,v;while(cin>>x>>y>>v&&x)a[x][y]=v;dp[0][1][1]=a[1][1];//要先赋初值 for(int k=1;k<=2*N-2;k++)for(int i1=1;i1<=min(k+1,N);i1++)for(int i2=1;i2<=min(k+1,N);i2++){dp[k][i1][i2]=Max(dp[k-1][i1][i2],dp[k-1][i1-1][i2],dp[k-1][i1][i2-1],dp[k-1][i1-1][i2-1]);dp[k][i1][i2]+=a[i1][k+2-i1];if(i1==i2)continue;//同一点只算一次dp[k][i1][i2]+=a[i2][k+2-i2]; }cout<<dp[2*N-2][N][N]<<endl;
}

滚动数组空间优化

#include"bits/stdc++.h"
using namespace std;
const int maxn=11;
int a[maxn][maxn];
int dp[2][maxn][maxn];//dp[k][i1][i2]走了k步第一次路径到了第i1行,第二次路径到了第i2行，然后纵坐标阔以用步数相减来计算 
int Max(int a,int b,int c,int d)
{return max(max(a,b),max(c,d));
}
int main()
{int N;cin>>N;int x,y,v;while(cin>>x>>y>>v&&x)a[x][y]=v;dp[0][1][1]=a[1][1];//要先赋初值int now=0,pre=0; for(int k=1;k<=2*N-2;k++){now=pre^1;for(int i1=1;i1<=min(k+1,N);i1++)for(int i2=1;i2<=min(k+1,N);i2++){dp[now][i1][i2]=Max(dp[pre][i1][i2],dp[pre][i1-1][i2],dp[pre][i1][i2-1],dp[pre][i1-1][i2-1]);dp[now][i1][i2]+=a[i1][k+2-i1];if(i1==i2)continue;//同一点只算一次dp[now][i1][i2]+=a[i2][k+2-i2]; }pre=now;}cout<<dp[now][N][N]<<endl;
}