對于m=1與m=2的情況分開單獨處理，m=2注意有4種不同的狀態

https://www.luogu.org/blog/ttt-ttt/solution-p2331

#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int INF=0x3f3f3f3f; const int maxn=105; const int maxk=15; int f[maxn][maxn][maxk]; int f1[maxn][maxk]; int sum[maxn]; int s1[maxn],s2[maxn]; int n,m,K,t; int main() {scanf("%d%d%d",&n,&m,&K);if(m==1){for(int i=1;i<=n;i++){int t;scanf("%d",&t);sum[i]=t+sum[i-1];}for(int i=1;i<=n;i++){for(int j=1;j<=K;j++){f1[i][j]=f1[i-1][j];for(int p=0;p<i;p++){f1[i][j]=max(f1[i][j],f1[p][j-1]+sum[i]-sum[p]);}}}printf("%d",f1[n][K]);}if(m==2){for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);s1[i]=s1[i-1]+x;s2[i]=s2[i-1]+y;}for(int k=1;k<=K;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);for(int l=0;l<i;l++) f[i][j][k]=max(f[i][j][k],f[l][j][k-1]+s1[i]-s1[l]);for(int l=0;l<j;l++)f[i][j][k]=max(f[i][j][k],f[i][l][k-1]+s2[j]-s2[l]);if(i==j){for(int l=0;l<i;l++)f[i][j][k]=max(f[i][j][k],f[l][l][k-1]+s1[i]-s1[l]+s2[j]-s2[l]);}}}}printf("%d",f[n][n][K]);}return 0; }

?

總結

以上是生活随笔為你收集整理的【题解】洛谷P2331 最大子矩阵（dp 前缀和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。