题解：P6235 [eJOI 2019] 矩形染色

为什么所有题解都直接做对角线，虽然本质一样，但你们这么用图论建模做不恶心吗？？？？

看到这种恶心的对角线，先考虑网格图上笛卡尔坐标转切比雪夫坐标（应该是这么说），即

(x,y)\to (x+y-1,x-y+m)

，注意这里是

1-\text{Index}

的。

那么我们考虑给原网格标个号，并且把它放到转换后的网格中找性质。

如下图，对

n=4,m=6

的情况进行标号。

可以发现，转换后的矩形是一个长宽均为

n+m-1

的正方形。并且，原图中的对角线覆盖全部对应着行/列覆盖。输入顺序正好就是先每一列的权值，再每一行的权值。

现在问题转化为有一个边长为

n+m-1

的正方形，可以覆盖每行每列，要用最少的代价覆盖所有不为

0

的网格。

可以发现一个性质，所有奇数行和偶数行完全没有关系，所以可以考虑分开做。

现在只考虑奇数行，如图：

可以先考虑选上所有行，然后再用列来替换。注意到每一行要求覆盖的都是列上的一段区间，因此如果可以不用覆盖一行，那么这行对应的区间列上面必须全部覆盖。

那么题意再次转化：有很多区间

[l_i,r_i]

，每个区间有权值

v_i

，选择每个点都有代价

w_i

，一个区间有贡献当且仅当区间内点都被选。最大化权值减代价。

这就很容易了，设

f_i

表示决策完前

i

个点的最大权值，那么有

f_i=\max_{j=1}^{i}f_{j-1}+\sum_{[l_k,r_k]\subseteq [j,i]}v_k-\sum_{k=j}^{i}w_k

。直接从左往右扫描线，线段树辅助维护一下就行了。

代码：

CPP

#include <bits/stdc++.h>
#define int long long
#define maxm 500005
#define maxn 1005
#define inf 0x3f3f3f3f3f3f
#define mod 1000000007
#define msk cerr
using namespace std;
int T,n,m,N,c1,c2,ans;
int a[maxn][maxn],b[maxn][maxn];
int sh[maxm],he[maxm];
int wei(int x){if(!x)return 1;int sum=0;while(x)x/=10,sum++;return sum;}
int L[maxm],R[maxm],s[maxm];
struct node{int l,r,w;}q[maxm];
struct srh{int l,w;};
vector<srh>ad[maxm];
int f[maxm],g[maxm];
struct Seg{int l,r,mx,add;}t[maxm<<2];
#define ls k<<1
#define rs k<<1|1
void Pushup(int k){t[k].mx=max(t[ls].mx,t[rs].mx);}
void Pushtag(int k,int x){t[k].mx+=x;t[k].add+=x;}
void Pushdown(int k){if(t[k].add)Pushtag(ls,t[k].add),Pushtag(rs,t[k].add),t[k].add=0;}
void Build(int k,int l,int r){
    t[k]=(Seg){l,r,0,0};if(l==r)return;
    int mid=l+r>>1;Build(ls,l,mid);Build(rs,mid+1,r);
}
void Add(int k,int l,int r,int x){
    if(t[k].l>r||t[k].r<l)return;
    if(t[k].l>=l&&t[k].r<=r)return Pushtag(k,x);
    Pushdown(k);Add(ls,l,r,x);Add(rs,l,r,x);Pushup(k);
}
int Ask(int k,int l,int r){
    if(t[k].l>r||t[k].r<l)return -inf;
    if(t[k].l>=l&&t[k].r<=r)return t[k].mx;
    Pushdown(k);return max(Ask(ls,l,r),Ask(rs,l,r));
}
int Sol(){//一开始钦定选所有横线
    int sum=0;Build(1,1,n+m-1);
    for(int i=1;i<=n+m-1;i++)ad[i].clear(),g[i]=f[i]=0,s[i]+=s[i-1];
    for(int i=1;i<=N;i++)ad[q[i].r].push_back({q[i].l,q[i].w}),sum+=q[i].w;
    for(int i=1;i<=n+m-1;i++){
        Add(1,i,i,f[i-1]+s[i-1]);
        for(srh p:ad[i])Add(1,1,p.l,p.w);
        f[i]=max(f[i-1],t[1].mx-s[i]);
    }
    return sum-f[n+m-1];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n+m-1;i++)cin>>sh[i],L[i]=n+m+1,R[i]=0;
    for(int i=1;i<=n+m-1;i++)cin>>he[i];
    for(int i=1;i<=n;i++){
        //(i,1)
        int x=i+1-1,y=i-1+m;
        L[x]=min(L[x],y);R[x]=max(R[x],y);
        //(i,m)
        x=i+m-1,y=i-m+m;
        L[x]=min(L[x],y);R[x]=max(R[x],y);
    }
    for(int i=1;i<=m;i++){
        //(1,i)
        int x=1+i-1,y=1-i+m;
        L[x]=min(L[x],y);R[x]=max(R[x],y);
        //(n,i)
        x=n+i-1,y=n-i+m;
        L[x]=min(L[x],y);R[x]=max(R[x],y);
    }
    for(int i=1;i<=n+m-1;i++)s[i]=0;
    for(int i=1;i<=n+m-1;i+=2)s[i]=sh[i];
    if(m&1)for(int i=1;i<=n+m-1;i+=2)q[++N]={L[i],R[i],he[i]};
    else for(int i=2;i<=n+m-1;i+=2)q[++N]={L[i],R[i],he[i]};
    ans+=Sol();
    N=0;
    for(int i=1;i<=n+m-1;i++)s[i]=0;
    for(int i=2;i<=n+m-1;i+=2)s[i]=sh[i];
    if(!(m&1))for(int i=1;i<=n+m-1;i+=2)q[++N]={L[i],R[i],he[i]};
    else for(int i=2;i<=n+m-1;i+=2)q[++N]={L[i],R[i],he[i]};
    
    ans+=Sol();
    cout<<ans;
    return 0;
    // for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=(i-1)*m+j,msk<<a[i][j]<<" \n"[j==m];
    // for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i+j-1][i-j+m]=a[i][j];
    // msk<<"======================\n";
    // for(int i=1;i<=n+m-1;i++){
    //     for(int j=1;j<=n+m-1;j++){
    //         int x=b[i][j];if(!(i&1))x=0;
    //         msk<<x<<" ";for(int k=1;k<=2-wei(x);k++)msk<<" ";
    //         if(j==n+m-1)msk<<"\n";
    //     }
    // }
}

题解：P6235 [eJOI 2019] 矩形染色

文章操作

相关推荐

评论

题解：P6235 [eJOI 2019] 矩形染色