双线程DP问题,
f[i][j][k][l]代表a走到i,j位置,b走到k,l位置的最大值。状态转移方程:
f[i][j][k][l]=max(max(max(f[i-1][j][k-1][l],f[i][j-1][k-1][l]),f[i-1][j][k][l-1]),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];
参考代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cmath> #include<vector> #include<set> #include<sstream> #include<cstring> #include<utility> using namespace std; typedef long long ll; typedef long l; const int N = 55; int n,m,a[55][55],f[N][N][N][N]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)scanf("%d",&a[i][j]); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int k=1;k<=n;k++){ for(int l=1;l<=m;l++){ f[i][j][k][l]=max(max(max(f[i-1][j][k-1][l],f[i][j-1][k-1][l]),f[i-1][j][k][l-1]),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][m][n][m]; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:629 |
聪明的美食家 (C语言代码)浏览:1258 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:690 |
C语言训练-求素数问题 (C语言代码)浏览:729 |
WU-蓝桥杯算法提高VIP-交换Easy (C++代码)浏览:1119 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:572 |
C语言训练-亲密数 (C语言描述,反正怎么都能对)浏览:2171 |
交换Easy (C语言代码)浏览:764 |
图形输出 (C语言代码)浏览:954 |
复数求和 (C语言代码)浏览:929 |