题解：【ABC298G】Strawberry War

· · 题解

稀碎的阅读体验

题目链接

场上被 F 干碎了，没看见这个典题。原题差不多是这个吧。

注意到矩形并不大，直接用最暴力的方法做就好。设 f_{t,x1,y1,x2,y2} 表示 (x1,y1) 到 (x2,y2) 这个区间切 t 刀所能获得的最小极差，然后暴力枚举当前这一刀是横着切还是竖着切，在哪个区间切，切在什么位置。我的实现使用了记搜以及前缀和快速计算区间和，需要注意的地方就是区间的开闭。

#include<bits/stdc++.h>
#define ld long double 
#define ull unsigned long long
#define int long long
#define pb push_back
#define mp make_pair
using namespace std;

inline int read()
{
    int s=0,w=1; char c=getchar();
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
    return s*w;
}
inline void write(int x,char ch)
{
    if(x<0) x=-x,putchar('-');
    static char stk[25]; int top=0;
    do {stk[top++]=x%10+'0',x/=10;} while(x);
    while(top) putchar(stk[--top]);
    putchar(ch);
    return;
}
inline void file()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
}

bool Mbe;

namespace MyTool
{
    static const int Mod=998244353;
    inline void Swp(int &a,int &b) {int t=a;a=b;b=t;}
    inline int  Max(int a,int b)   {return (b&((a-b)>>63))|(a&(~(a-b)>>31));}
    inline int  Min(int a,int b)   {return (a&((a-b)>>63))|(a&(~(a-b)>>31));}
    template<typename T> inline void cmax(T &a,T b) {a=a>b?a:b;}
    template<typename T> inline void cmin(T &a,T b) {a=a<b?a:b;}
    inline int  Abs(int a) {return (a^(a>>63))-(a>>63);}
    inline void Madd(int &a,int b) {a=a+b>Mod?a+b-Mod:a+b;}
    inline void Mdel(int &a,int b) {a=a-b<0?a-b+Mod:a-b;}
    inline void Mmul(int &a,int b) {a=1ll*a*b%Mod;}
    inline void Mmod(int &a) {a=(a%Mod+Mod)%Mod;}
    inline int  Cadd(int a,int b)  {return a+b>=Mod?a+b-Mod:a+b;}
    inline int  Cdel(int a,int b)  {return a-b<0?a-b+Mod:a-b;}
    inline int  Cmul(int a,int b)  {return a*b%Mod;}
    inline int  Cmod(int a)  {return (a%Mod+Mod)%Mod;}
    inline int  gcd(int a,int b)   {return b?gcd(b,a%b):a;}
    inline int  qpow(int a,int b)  {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
    inline int  qmul(int a,int b)  {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
    template<typename T> inline T pow(T x)    {return x*x;}
}
using namespace MyTool;

namespace LgxTpre
{
    static const int MAX=10;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    static const int mod=1e9+7;
    static const int bas=131;

    int n,m,t;
    int num[MAX][MAX],sum[MAX][MAX];
    int vis[MAX*MAX][MAX][MAX][MAX][MAX];
    pair<int,int> ans,dp[MAX*MAX][MAX][MAX][MAX][MAX];

    pair<int,int> dfs(int T,int x,int y,int x_,int y_)
    {
        pair<int,int> &tmp=dp[T][x][y][x_][y_];
        if(vis[T][x][y][x_][y_]) return tmp;
        vis[T][x][y][x_][y_]=1;
        if(!T) return tmp=mp(sum[x_][y_]-sum[x-1][y_]-sum[x_][y-1]+sum[x-1][y-1],sum[x_][y_]-sum[x-1][y_]-sum[x_][y-1]+sum[x-1][y-1]);
        tmp=mp(-INF,INF);
        for(int k=0;k<T;++k)
            for(int i=x;i<x_;++i)
            {
                pair<int,int> L=dfs(k,x,y,i,y_),R=dfs(T-k-1,i+1,y,x_,y_);
                if(tmp.second-tmp.first>max(L.second,R.second)-min(L.first,R.first))
                    tmp=mp(min(L.first,R.first),max(L.second,R.second));
            }
        for(int k=0;k<T;++k)
            for(int i=y;i<y_;++i)
            {
                pair<int,int> L=dfs(k,x,y,x_,i),R=dfs(T-k-1,x,i+1,x_,y_);
                if(tmp.second-tmp.first>max(L.second,R.second)-min(L.first,R.first))
                    tmp=mp(min(L.first,R.first),max(L.second,R.second));
            }
        return tmp;
    }

    inline void mian()
    {
        n=read(),m=read(),t=read();
        for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) num[i][j]=read(),sum[i][j]=num[i][j]-sum[i-1][j-1]+sum[i][j-1]+sum[i-1][j];
        ans=dfs(t,1,1,n,m);
        write(ans.second-ans.first,'\n');
        return;
    }
}

bool Med;

signed main()
{
//  file();
    fprintf(stderr,"%.3lf MB\n",(&Med-&Mbe)/1048576.0);
    LgxTpre::mian();
    cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
    return (0-0);
}