P3120 [USACO15FEB] Cow Hopscotch G 题解

STUDENT00 · 2024-11-19 21:12:03 · 题解

小清新暴力题。

首先，如果排除限制“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)。

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

#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;
}