题解：P3120 [USACO15FEB] Cow Hopscotch G

分析

首先可以想到最朴素的 DP：

f_{i,j}

表示

(i,j)

对答案产生的贡献，则有转移方程：

f_{i,j}=\sum_{k=1}^{i-1}\sum_{l=1}^{j-1}[a_{i,j}\not= a_{k,l}]f_{k,l}

时间复杂度

O(n^4)

，需要优化，最首先能想到的显然是二维线段树，但会发现这样空间和时间都会爆掉。

考虑类似 DP 处理的过程，按行来处理，建

k+1

棵线段树，每个节点维护列

[l,r]

中该值的贡献和，第

0

棵节点维护所有值的贡献和，对每行处理时，先统计答案再最后一起修改，这样就保证了线段树里的贡献均不包括当前行的贡献。

但是这样直接建立线段树空间要爆炸，动态开点即可。

普通版本：

CPP

#include<bits/stdc++.h>
#define mod 1000000007
#define _ 755
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int n,m,k,a[_][_],now[_];
struct seg{
	int t[_<<2];
	void pushup(int num){t[num]=(t[num<<1]+t[num<<1|1])%mod;}
	void update(int l,int r,int num,int x,int y){
		if(x>r||x<l)return;
		if(x==l&&x==r){t[num]=(t[num]+y)%mod;return;}
		int mid=l+r>>1;
		update(l,mid,num<<1,x,y),update(mid+1,r,num<<1|1,x,y);
		pushup(num);
	}
	int query(int l,int r,int num,int x,int y){
		if(x>r||y<l)return 0;
		if(x<=l&&r<=y)return t[num];
		int mid=l+r>>1;
		return (query(l,mid,num<<1,x,y)+query(mid+1,r,num<<1|1,x,y))%mod;
	}
}t[_*_];
int main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=read();
	t[0].update(1,m,1,1,1),t[a[1][1]].update(1,m,1,1,1);
	for(int i=2;i<=n;i++){
		for(int j=2;j<=m;j++){
			now[j]=(t[0].query(1,m,1,1,j-1)+mod-t[a[i][j]].query(1,m,1,1,j-1))%mod;
		}
		for(int j=1;j<=m;j++){
			t[0].update(1,m,1,j,now[j]);
			t[a[i][j]].update(1,m,1,j,now[j]);
		}
	}
	printf("%d\n",now[m]);
	return 0;
}

动态开点版本：

CPP

#include<bits/stdc++.h>
#define mod 1000000007
#define _ 755
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int n,m,k,a[_][_],now[_],rt[_*_];
struct seg{
	int t[_*_<<5],tot,ls[_*_<<5],rs[_*_<<5];
	void pushup(int num){t[num]=(t[ls[num]]+t[rs[num]])%mod;}
	void update(int l,int r,int &num,int x,int y){
		if(!num)num=++tot;
		if(x>r||x<l)return;
		if(x==l&&x==r){t[num]=(t[num]+y)%mod;return;}
		int mid=l+r>>1;
		update(l,mid,ls[num],x,y),update(mid+1,r,rs[num],x,y);
		pushup(num);
	}
	int query(int l,int r,int &num,int x,int y){
		if(!num)num=++tot;
		if(x>r||y<l)return 0;
		if(x<=l&&r<=y)return t[num];
		int mid=l+r>>1;
		return (query(l,mid,ls[num],x,y)+query(mid+1,r,rs[num],x,y))%mod;
	}
}t;
int main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=read();
	t.update(1,m,rt[0],1,1),t.update(1,m,rt[a[1][1]],1,1);
	for(int i=2;i<=n;i++){
		for(int j=2;j<=m;j++){
			now[j]=(t.query(1,m,rt[0],1,j-1)+mod-t.query(1,m,rt[a[i][j]],1,j-1))%mod;
		}
		for(int j=1;j<=m;j++){
			t.update(1,m,rt[0],j,now[j]);
			t.update(1,m,rt[a[i][j]],j,now[j]);
		}
	}
	printf("%d\n",now[m]);
	return 0;
}

题解：P3120 [USACO15FEB] Cow Hopscotch G

文章操作

分析

相关推荐

评论

题解：P3120 [USACO15FEB] Cow Hopscotch G