SCOI2005]最大子矩阵(dp)

一开始思路错了，想着把k当成1 求了一个最大子矩阵
然后对最大子矩阵所在的一行用最大k段子序列，后来发现思路错了，因为这样所求的子矩阵的终点行一定都相同了
正确的思路：
因为m（列）是1<=m<=2，只有两种情况，对于m==1时候就是个竖着的最大k段子序列的和，

        dp[i][x][y]
        在第一列的1-x行选择
        在第二列的1-y行选择
        共选择i个矩阵
        1.假如选择第（x,1） 不选（y,2） max(dp[i-1][t][y]+a[x][1]-a[t-1][1],dp[i][x][y] )
        2.假如不选择第（x,1） 选（y,2）max(dp[i-1][x][t]+a[y][2]-a[t-1][2],dp[i][x][y] )
        3.假如选择第（x,1） 选（y,2）max(dp[i-1][t][t]+a[x][1]-a[t-1][1]+a[y][2]-a[t-1][2],dp[i][x][y] )

代码

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const int maxn=2e5+66;
const ll mod = 911451407;
const int N =1e6+3;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
ll n,m,k,a[121][121],b[121],pre[121],dp[121][121][121],d[121],s[1212][125];
int UpMing() {
    n=read(),m=read(),k=read();
    rep(i,1,n) rep(j,1,m) s[i][j]=a[i][j]=read(),a[i][j]+=a[i-1][j];
    if(m==1) {
        for(int i=1 ; i<=n ; i++)
            b[i]=s[i][1],b[i]+=b[i-1];

        mst(s,0);
        for(int i=1 ; i<=k ; i++) {
            for(int j=1 ; j<=n ; j++) {
                for(int t=0 ; t<j ; t++) {
                    s[i][j]=max(s[i][j-1],s[i][j]);
                    s[i][j]=max(s[i][j],s[i-1][t]+b[j]-b[t]);
                }
            }
        }

    } else {
        for(int i=1 ; i<=k ; i++) {
            for(int j=1; j<=n ; j++) {
                for(int t=1 ; t<=n ; t++) {
                    dp[i][j][t]=max(max(dp[i][j-1][t],dp[i][j][t-1]),dp[i][j-1][t-1]);
                    for(int p=0 ; p<j; p++)    dp[i][j][t]=max(dp[i][j][t],dp[i-1][p][t]+a[j][1]-a[p][1]);
                    for(int p=0 ; p<t; p++)    dp[i][j][t]=max(dp[i][j][t],dp[i-1][j][p]+a[t][2]-a[p][2]);
                    if(j==t) for(int p=0 ; p<j; p++) dp[i][j][t]=max(dp[i][j][t],dp[i-1][p][p]+a[j][1]-a[p][1]+a[t][2]-a[p][2]);
                }
            }
        }
        out(dp[k][n][n]);
    }

    Accept;
}

m==1时候优化算法

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const int maxn=2e5+66;
const ll mod = 911451407;
const int N =1e6+3;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
ll n,m,k,a[121][121],b[121],pre[121],dp[121][121][121],d[121],s[1212][125];
int UpMing() {
    n=read(),m=read(),k=read();
    rep(i,1,n) rep(j,1,m) s[i][j]=a[i][j]=read(),a[i][j]+=a[i-1][j];
    if(m==1) {
        for(int i=1 ; i<=n ; i++)
            b[i]=s[i][1];

            ll temp;
            for(int i=1 ; i<=k ; i++) {
                temp=-inf;
                for(int j=i ; j<=n ; j++) {
                    d[j]=max(d[j-1],pre[j-1])+b[j];
                    pre[j-1]=temp;
                    temp=max(temp,d[j]);
                }
            }
            cout<<temp<<endl;

    } else {
        for(int i=1 ; i<=k ; i++) {
            for(int j=1; j<=n ; j++) {
                for(int t=1 ; t<=n ; t++) {
                    dp[i][j][t]=max(max(dp[i][j-1][t],dp[i][j][t-1]),dp[i][j-1][t-1]);
                    for(int p=0 ; p<j; p++)  dp[i][j][t]=max(dp[i][j][t],dp[i-1][p][t]+a[j][1]-a[p][1]);
                    for(int p=0 ; p<t; p++)  dp[i][j][t]=max(dp[i][j][t],dp[i-1][j][p]+a[t][2]-a[p][2]);
                    if(j==t) for(int p=0 ; p<j; p++) dp[i][j][t]=max(dp[i][j][t],dp[i-1][p][p]+a[j][1]-a[p][1]+a[t][2]-a[p][2]);
                }
            }
        }
        out(dp[k][n][n]);
    }

    Accept;
}