题解 P7716 【「EZEC-10」Covering】
绝顶我为峰
·
·
题解
非常明显的，这是一个 dp 题目。
发现 $k$ 并没有什么用，因为实际上我们只能编号不超过棋盘中最大的编号，记作 $maxn$。
考虑转移，分情况讨论：
- $i$ 在棋盘上出现了两次：显然纸片只能放在固定一个位置，$dp_{i,j}=dp_{i-1,j-1}$。
- $i$ 在棋盘上出现了一次：纸片的一端固定在这个点，另一端可以在上下左右四个点选取，但因为 $i$ 最终被覆盖了，所以上下左右可选的点必须编号比 $i$ 大。记合法数量为 $tag$，那么 $dp_{i,j}=tag·dp_{i-1.j-1}$。
- $i$ 没有在棋盘上出现：这时可选可不选，不选显然直接对应转移，关键是如果选了这个纸片，我们要计算可以放这个纸片的位置有多少。我们发现必须要相邻两个点的编号均大于 $i$，纸片才能放在这里。也就是说，我们假设相邻两点的编号较小值是 $p$，那么这个位置会对 $1\sim p-1$ 的位置产生贡献，这个可以求一遍前缀和简单地得到。于是这个转移也是 $O(1)$ 的，记刚才预处理的可放位置是 $sum_i$，那么 $dp_{i,j}=dp_{i-1,j}+sum_i·dp_{i-1,j-1}$。
然后需要注意一下下界的选取。因为出现在棋盘上的编号是必须选取的，我们需要统计这个数字，记作 $cnt$，转移的时候强制从 $cnt+1$ 开始转移，否则会出错。
最后，答案就是 $\sum_{i=\max{l,cnt}}^rdp_{maxn,i}$。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
const int mod=1000000007;
int t,n,m,k,l,r,dp[2001][2001],mp[2001][2001],sum[20005],maxn,ans,cnt;
pair<int,int> vis[20001];
inline int read()
{
int x=0;
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;
}
signed main()
{
t=read();
while(t--)
{
n=read(),m=read(),k=read(),l=read(),r=read();
memset(sum,0,sizeof sum);
memset(vis,0,sizeof vis);
memset(dp,0,sizeof dp);
memset(mp,0,sizeof mp);
maxn=cnt=0;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
{
mp[i][j]=read();
if(!mp[i][j])
continue;
maxn=max(maxn,mp[i][j]);
vis[mp[i][j]]=make_pair(i,j);
if(i>1&&mp[i-1][j])
++sum[min(mp[i-1][j],mp[i][j])];
if(j>1&&mp[i][j-1])
++sum[min(mp[i][j-1],mp[i][j])];
}
for(register int i=k;i>=1;--i)
sum[i]=(sum[i]+sum[i+1])%mod;
dp[0][0]=1;
for(register int i=1;i<=maxn;++i)
if(vis[i].first)
{
for(register int j=0;j<cnt;++j)
dp[i][j]=0;
dp[i][cnt]=dp[i-1][cnt];
int x=vis[i].first,y=vis[i].second;
if(mp[x-1][y]==i||mp[x+1][y]==i||mp[x][y-1]==i||mp[x][y+1]==i)
{
for(register int j=cnt+1;j<=r;++j)
dp[i][j]=dp[i-1][j-1];
++cnt;
continue;
}
int tag=(mp[x-1][y]>i)+(mp[x+1][y]>i)+(mp[x][y-1]>i)+(mp[x][y+1]>i);
for(register int j=cnt+1;j<=r;++j)
dp[i][j]=tag*dp[i-1][j-1]%mod;
++cnt;
}
else
{
dp[i][cnt]=dp[i-1][cnt];
for(register int j=0;j<cnt;++j)
dp[i][j]=0;
for(register int j=cnt+1;j<=r;++j)
dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*sum[i]%mod)%mod;
}
ans=0;
for(register int i=max(cnt,l);i<=r;++i)
ans=(ans+dp[maxn][i])%mod;
printf("%lld\n",ans);
}
return 0;
}
```