P3120 [USACO15FEB] Cow Hopscotch G 题解

小清新暴力题。

首先，如果排除限制“B 格子的标号和 A 格子的标号不同”，是一个典中典的简单 DP。

加上限制后，考虑用加上前的得数减去“B 格子的标号和 A 格子的标号相同”的，得到正确答案。

怎么做呢？显然可以使用一个桶，对于每一行分别处理。具体的，遍历到

(x,y)

时，

val_k

中存储的是

\sum\limits_{i=1}^{x-1}\sum\limits_{j=1}^{y-1}[a_{i,j}=a_{x,y}]f_{i,j}

。我们在

(i,n)\rightarrow (i+1,1)

时，清空

val

数组；在

(i,j)\rightarrow (i,j+1)

时，加入

f_{1\sim i-1,j}

。总时间复杂度

O(n^2m)

。

加上一些快读和卡常，即可通过。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=760;
const int mod=1000000007;
int n,m,k,a[N][N],val[N*N],f[N][N];
inline int read(){
	char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	int x=0;
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
inline void add(int &x,int y){
	((x+=y)>=mod?x-=mod:0);
}
inline int sub(int x,int y){
	return x-y+(x<y?mod:0);
} 
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();
	f[1][1]=1;
	for(int i=2;i<=n;i++){
		int res=0;
		memset(val,0,sizeof(val));
		for(int j=2;j<=m;j++){
			for(int k=1;k<i;k++) add(val[a[k][j-1]],f[k][j-1]),add(res,f[k][j-1]); 
			f[i][j]=sub(res,val[a[i][j]]);
		}
	}
	printf("%d",f[n][m]);
	return 0;
}

P3120 [USACO15FEB] Cow Hopscotch G 题解

文章操作

相关推荐

评论

P3120 [USACO15FEB] Cow Hopscotch G 题解