专栏文章

题解：P1398 [NOI2013] 书法家

yyisit
P1398题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip30zh0
此快照首次捕获于
2025/12/03 05:20
3 个月前
此快照最后确认于
2025/12/03 05:20
3 个月前
查看原文

题解：P1398 [NOI2013] 书法家

原题

题意

在网格上写 NOI，每个格子上有一些权值，要求覆盖的权值最大，书写有一些规则。

Solution

将 NOI 分成 11 个部分，每个部分都是有几个有相同特点的矩形构成的，按列 dp 前缀最大值优化一下即可。看起来很难码的样子，其实套路都差不多，但是想清楚，一些细节处理到位，平时习惯好一点就可以很快写完辣。

预处理

  • f[p][i][j][k]f[p][i][j][k] 表示 pp 个部分，正在 dp 第 ii 列，矩形上边界为 jj，下边界为 kk 时的最大权值。
  • mx[p][i][j][k]mx[p][i][j][k] 表示 pp 个部分，正在 dp 第 ii 列，矩形上边界为 jj，下边界为 kk 相关的前缀最大值。
其实比较恶心的就是第二部分，你需要处理出这样的一个前缀最大值：上边界的区间在 [1,j][1,j]，边界的区间在 [j+1,k][j+1,k]， 这个并不好直接求出来，所以我们把它分成两部分：上边界区间在 [1,j][1,j]，下边界固定在 j+1j+1；以及上边界在 [1,j][1,j]，下边界在 [j,k][j,k]。这样就肥肠煎蛋了。

代码

CPP
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>
#define LL long long
#define inf (1ll<<30)
#define MOD 1000000007
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
 
const int maxn=160,maxm=510;
int a[maxn][maxm],s[maxm][maxn],up[maxn];
int f[12][maxn][maxn],g[12][maxn][maxn],mx[12][maxn][maxn];
int n,m;
 
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 j=1;j<=m;j++)
        for (int i=1;i<=n;i++) s[j][i]=s[j][i-1]+a[i][j];
    for (int i=0;i<=11;i++)
        for (int j=0;j<=n+1;j++)
            for (int k=0;k<=n+1;k++) f[i][j][k]=g[i][j][k]=mx[i][j][k]=-inf;
    for (int i=0;i<=n+1;i++) up[i]=-inf;
    int ans=-inf;
    for (int i=1;i<=m;i++) {
        //第1部分
        for (int j=1;j<=n;j++)
            for (int k=j;k<=n;k++)
                f[1][j][k]=max(g[1][j][k],0)+s[i][k]-s[i][j-1];
        //第2部分
        for (int j=1;j<=n;j++)
            for (int k=n;k>=j;k--) mx[1][j][k]=max(g[1][j][k],mx[1][j][k+1]);
        for (int k=1;k<=n;k++) {
            up[k]=-inf;
            for (int j=1;j<=k;j++) up[k]=max(up[k],g[2][j][k]);
        }
        for (int k=1;k<=n;k++)
            for (int j=1;j<=k;j++) mx[2][j][k]=max(mx[2][j-1][k],g[2][j][k]);
        for (int j=1;j<=n;j++)
            for (int k=j;k<=n;k++) mx[2][j][k]=max(mx[2][j][k-1],mx[2][j][k]);
        for (int j=1;j<=n;j++)
            for (int k=j;k<=n;k++)
                f[2][j][k]=max(up[j-1],max(mx[1][j][k+1],mx[2][j][k]))+s[i][k]-s[i][j-1];
        //第3部分
        for (int k=1;k<=n;k++)
            for (int j=k;j>=1;j--) mx[2][j][k]=max(mx[2][j+1][k],g[2][j][k]);
        for (int j=1;j<=n;j++)
            for (int k=j;k<=n;k++)
                f[3][j][k]=max(g[3][j][k],mx[2][j+1][k])+s[i][k]-s[i][j-1];
        //第4部分
        f[4][0][0]=g[4][0][0];
        for (int j=1;j<=n;j++)
            for (int k=j;k<=n;k++) f[4][0][0]=max(f[4][0][0],g[3][j][k]);
        //第5部分
        for (int j=1;j<=n;j++)
            for (int k=j+2;k<=n;k++) f[5][j][k]=g[4][0][0]+s[i][k]-s[i][j-1];
        //第6部分
        for (int j=1;j<=n;j++)
            for (int k=j+2;k<=n;k++) f[6][j][k]=max(g[5][j][k],g[6][j][k])+s[i][j]-s[i][j-1]+s[i][k]-s[i][k-1];
        //第7部分
        for (int j=1;j<=n;j++)
            for (int k=j+2;k<=n;k++) f[7][j][k]=g[6][j][k]+s[i][k]-s[i][j-1];
        //第8部分
        f[8][0][0]=g[8][0][0];
        for (int j=1;j<=n;j++)
            for (int k=j+2;k<=n;k++) f[8][0][0]=max(f[8][0][0],g[7][j][k]);
        //第9部分
        for (int j=1;j<=n;j++)
            for (int k=j+2;k<=n;k++) f[9][j][k]=max(g[9][j][k],g[8][0][0])+s[i][j]-s[i][j-1]+s[i][k]-s[i][k-1];
        //第10部分
        for (int j=1;j<=n;j++)
            for (int k=j+2;k<=n;k++) f[10][j][k]=max(g[10][j][k],g[9][j][k])+s[i][k]-s[i][j-1];
        //第11部分
        for (int j=1;j<=n;j++)
            for (int k=j+2;k<=n;k++) {
                f[11][j][k]=max(g[10][j][k],g[11][j][k])+s[i][j]-s[i][j-1]+s[i][k]-s[i][k-1];
                ans=max(ans,f[11][j][k]);
            }
        //滚动
        for (int j=1;j<=11;j++)
            for (int k=0;k<=n;k++)
                for (int l=0;l<=n;l++) g[j][k][l]=f[j][k][l];
    }
    printf("%d\n",ans);
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...