P3120 题解

lgvc · 2022-08-25 18:29:36 · 题解

这是一篇不需要高级算法，数据结构的 O(R^2C) 做法。

首先考虑暴力的 dp，f_{i,j} 表示从 (1,1) 走到 (i,j) 的方案数，可以进行 O(RC) 的转移，无法通过。

考虑在 dp 的时候，先枚举 i，再枚举 j，然后枚举到 j 的时候把所有的第 j-1 列，行数小于 i 的点暴力插入（具体的，使用一个桶记录所有的用颜色 i 结尾的方案数），同时维护桶内的数的和。转移就可以用和减去以自己的颜色结尾的方案数量。时间复杂度 O(R^2C)，需稍加常数优化并开起 O2 才可以通过。

代码：

#include <bits/stdc++.h>
#define MOD 1000000007
static char buf[1000000],*paa=buf,*pd=buf;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline int read(void) {
    register int x(0);register char c(getchar());
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}
int R,C,K,dp[759][759],a[759][759];
long long v[759*759];
signed main(void) {
    R=read();C=read();K=read();
    for(int i=1;i<=R;i++) {
        for(int j=1;j<=C;j++) {
            a[i][j]=read();
        }
    }
    dp[1][1]=1;
    for(int i=2;i<=R;i++) {
        memset(v,0,sizeof(v));
        long long as=0;
        for(int j=2;j<=C;j++) {
            for(int k=1;k<i;k++) {
                v[a[k][j-1]]+=dp[k][j-1];
                as+=dp[k][j-1];
            }
            dp[i][j]=((as-v[a[i][j]])%MOD+MOD)%MOD;
        }
    }
    printf("%d",dp[R][C]);
    return 0;
}