P2092 来聊聊<折形最大>

by 2021tyoi0037——2022-04-12 22:17:18

返回

很淼的DP题而已 不过还是详细分析一下吧 ---- 要求矩阵中折形的最大和 第一反应是动态规划的方法来求解 每一个折形可以被拆成三个部分: 向上的最大连续子序列和 向左的最大连续子序列和 折点（也就是折形的右下角) 然后分开算DP就行了 注意：开long long，不然 `WA 95分` 祝大家AC #include <iostream> #include <queue> #include <cstdio> using namespace std; long long u[1007][1007],l[1007][1007],a[1007][1007],n,m,ans=-99999999; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; u[i][j]=max(u[i-1][j]+a[i][j],a[i][j]); l[i][j]=max(l[i][j-1]+a[i][j],a[i][j]); } } for(int i=2;i<=n;i++){ for(int j=2;j<=m;j++){ ans=max(ans,u[i-1][j]+l[i][j-1]+a[i][j]); } } cout<<ans; return 0; }

赞(3)

+1