双线程 线性dp 传纸条

/* 两种做法：一是暴力dp[i][j][k][l] 二是以走的步数k作为阶段， dp[k][i][j]表示走到第k步，第一个人横坐标走到i，第二个人横坐标走到j 可以以此推出第第一个人的坐标为[i,k-i+1],第二个人坐标[j,k-j+1] 状态转移方程 dp[k][i][j]=max(dp[k-1][i][j],dp[k-1][i-1][j],dp[k-1][i][j-1],dp[k-1][i-1][j-1])+ mp[i][k-i+1]+mp[j][k-j+1] */ #include<bits/stdc++.h> using namespace std; #define maxn 205 int mp[maxn][maxn],dp[maxn][maxn][maxn],n,m; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]); memset(dp,0,sizeof dp); dp[1][1][1]=mp[1][1]; for(int k=2;k<=m+n-1;k++){//从第二步开始计算 int mm=min(k,m);//最远可以到的横坐标 for(int i=1;i<=mm;i++) for(int j=1;j<=mm;j++){ int max1=max(dp[k-1][i][j],dp[k-1][i-1][j]); int max2=max(dp[k-1][i-1][j],dp[k-1][i-1][j-1]); if(i==j) dp[k][i][j]=max(max1,max2)+mp[j][k-j+1]; else dp[k][i][j]=max(max1,max2)+mp[i][k-i+1]+mp[j][k-j+1]; } } printf("%d\n",dp[m+n-1][m][m]); return 0; }

 

转载于:https://www.cnblogs.com/zsben991126/p/10216124.html

相关资源：各显卡算力对照表！