螞蟻尋路（bzoj3111&ZJOI2013）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k;
int xx;
int f[120][25][120];
int g[120][25][120][2];
int s[120][120]; 
int main(){
    scanf("%d%d%d",&n,&m,&k);
    k=k*2+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&xx);
            s[i][j]=s[i-1][j]+xx;
        }
    }
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            f[0][i][j]=g[0][i][j][0]=g[0][i][j][1]=0xc0c0c0c0;
        }
    }
    int ans=0xc0c0c0c0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int p=1;p<=k;p++){
                for(int h=1;h<=i;h++){
                    f[j][p][h]=max(f[j-1][p][h],g[j-1][p-1][h][p%2])+s[i][j]-s[i-h][j];
                }
                g[j][p][i][0]=0xc0c0c0c0;
                for(int h=i-1;h>0;h--){
                    g[j][p][h][0]=max(g[j][p][h+1][0],f[j][p][h+1]);
                }
                g[j][p][1][1]=0xc0c0c0c0;
                for(int h=2;h<=i;h++){
                    g[j][p][h][1]=max(g[j][p][h-1][1],f[j][p][h-1]);
                }

            }
            ans=max(ans,max(f[j][k][i],g[j][k][i][1]));
        }
    }
    printf("%d",ans);
    return 0;
}