自动搬运

查看原文

来自洛谷，原作者为

	绝顶我为峰 蓝的盆。

搬运于2025-08-24 22:32:26，当前版本为作者最后更新于2021-07-12 12:19:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

非常明显的，这是一个 dp 题目。

$n,m,k\leq10^3$，允许我们设计二维状态来 dp。记 $dp_{i,j}$ 表示在前 $i$ 个纸片中选择 $j$ 个的方案数。

发现 $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}$。

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