P2140 记忆化搜索

· · 题解

题意：纵横划分区域，使得除去某一区域的值后其他区域的和不超过 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;
}