自动搬运

查看原文

来自洛谷，原作者为

	Usada_Pekora 兎田ぺこら/大傻Peko_Official/AFO

搬运于2025-08-24 21:34:25，当前版本为作者最后更新于2021-11-24 12:39:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：纵横划分区域，使得除去某一区域的值后其他区域的和不超过 $u$ 。

思路：用 dfs 划分区域，如果沿着当前轴划分是可行的，那么再对划分后的区域进行 dfs 。

但是这样做的时间成本是很高的， 因为这种做法对同一区间做了重复的计算，这个时候就考虑用数组记录某一区间的最优值，在产生重复计算时直接调用即可。 设 $f[x1][y1][x2][y2]$ 表示 $(x1,y1)$ 到 $(x2,y2)$ 的最优划分，则答案是 $f[1][1][n][m]$ 。

代码如下。

#include<bits/stdc++.h>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
typedef pair<int,int> pii;
inline int read(){
    int x = 0;char ch = getchar();
    while(ch < '0' || ch > '9'){ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x<<1)+(x<<3)+(ch^48);ch = getchar();}
    return x;
}
int n,m,u,a[35][35],sum = 0,s[35][35];
pii f[35][35][35][35];
#define calc(x1,y1,x2,y2) (s[x2][y2]+s[x1-1][y1-1]-s[x1-1][y2]-s[x2][y1-1])
inline pii dfs(int x1,int y1,int x2,int y2,int all){
    if(f[x1][y1][x2][y2].first) return f[x1][y1][x2][y2];
    if(x1 == x2 && y1 == y2) return pii{1,u-(sum-all)};
    pii t;t.first = 1,t.second = u-(sum-all);
    for(register int i = y1;i < y2;++i){
        int s1 = calc(x1,y1,x2,i),s2 = calc(x1,i+1,x2,y2);
        if(sum-s1 <= u && sum-s2 <= u){
            pii p1 = dfs(x1,y1,x2,i,s1),p2 = dfs(x1,i+1,x2,y2,s2);
            if(p1.first+p2.first > t.first)t.first = p1.first+p2.first,t.second = min(p1.second,p2.second);
            else if(p1.first+p2.first == t.first) t.second = max(t.second,min(p1.second,p2.second));
        }
    }
    for(register int i = x1;i < x2;++i){
        int s1 = calc(x1,y1,i,y2),s2 = calc(i+1,y1,x2,y2);
        if(sum-s1 <= u && sum-s2 <= u){
            pii p1 = dfs(x1,y1,i,y2,s1),p2 = dfs(i+1,y1,x2,y2,s2);
            if(p1.first+p2.first > t.first)t.first = p1.first+p2.first,t.second = min(p1.second,p2.second);
            else if(p1.first+p2.first == t.first) t.second = max(t.second,min(p1.second,p2.second));
        }
    }
    return f[x1][y1][x2][y2] = t;
}
int main(){
    n = read(),m = read(),u = read();
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= m;++j) a[i][j] = read(),sum += a[i][j];
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= m;++j) s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
    pii ans = dfs(1,1,n,m,sum);
    printf("%d %d",ans.first,ans.second);
    return 0;
}