U292735 Create a Better Function

题面
出题人：Coding_Hong

题意解释

我们发现A数组其实就是个下标

从B数组中选出n个数，使它相邻两个数之差的绝对值小于等于$t$

问总共有几种方案

题目思路

很明显是个$DP$题

首先想想状态的设计

可以用$f[i][j]$表示前i个数已经决定完了，且最后一位是$j$的方案数

那么最终的答案就是$f[n][k]$ $k\in$ 1~n之和呗

首先进行一个初始化$dp[1][k]$=1，因为只有一个数，方案数只能是1

枚举 $i$ $1 \to n$

枚举 $j$ $1 \to num$（num指最大的数，最大的数能枚举到那么所有的数就都能枚举到，这里不枚举$1 \to n$是防止B集合有的数枚举不到，我们枚举的是数字，不是个数）

因为B数组不是连续的，肯定有的数B数组都没有，所以输入的时候要标记一下

所以读入的时候就可以提前求出来

然后枚举一个$k$

因为最后一位是j，我们现在要往它的后面加一个$k$

所以符合if(vis[j]&&abs(j-k)>=t)那么就可以转移

转移：dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;（$mod$是要$define$的一个模数$1e9+7$）

然后定义一个ans

枚举求一下和

然后…… 然后你就会获得一份50分的代码

50分代码：

#include<bits/stdc++.h>
#define int long long
const int maxn=5050;
const int mod=1e9+7;
using namespace std;
int n,m,t,num;
int dp[maxn][maxn],a[maxn],vis[maxn];
signed main(){
    cin>>n>>m>>t;
    for(int i=1;i<=m;i++)cin>>a[i],num=max(num,a[i]),vis[a[i]]=1;
    sort(a+1,a+1+m);//小优化
    for(int i=1;i<=m;i++)
        dp[1][a[i]]=1;
    for(int i=2;i<=n;i++)//因为dp[1][k]已经预处理过了,所以从2开始枚举.
	{
        for(int j=1;j<=num;j++)
            for(int k=1;k<=num;k++)
                if(vis[j]&&abs(j-k)>=t)
                    dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
    }
    int ans=0;
    for(int i=1;i<=num;i++)
        ans=(ans+dp[n][i])%mod;
    cout<<ans<<endl;
    return 0;
}

显然，$5000^3$过不了

那么可以怎么优化呢？

看下限制条件if(vis[j]&&abs(j-k)>=t)

转化一下就是k<=j-t或k>=j+t

枚举的是$j$,$t$是定值，那么就可以抽象成一个区间移动

区间移动怎么移动的？

举个栗子

加入现在知道$1 \to 5$的区间和

要求$2 \to 6$的区间和

做法就是减去$1$再加上$6$

区间内的就是一定不符合条件的值，因为和j的绝对值之差小于$t$

所以我们只需要求两个值：$tot$和$b$

$tot$就是原来所有的方案数之和

$b$就是要减去的不符合条件的

那么$tot-b$就是要加上的

那么怎么求呢

$tot$枚举一遍就可以了

$b$只需要初始化一个初始区间($1 \to t-1$)

然后移动区间（删左加右）就可以了

注意防止越界

其它细节见代码注释

代码如下：

#include<bits/stdc++.h>
#define int long long //好评
const int maxn=5050;
const int mod=1e9+7;
using namespace std;
int n,m,t,num;
int dp[maxn][maxn],a[maxn],vis[maxn];
signed main(){
    cin>>n>>m>>t;
    for(int i=1;i<=m;i++)cin>>a[i],num=max(num,a[i]),vis[a[i]]=1;
    sort(a+1,a+1+m);//小优化
    for(int i=1;i<=m;i++)//初始化
        dp[1][a[i]]=1;
    for(int i=2;i<=n;i++)//因为dp[1][k]已经预处理过了,所以从2开始枚举.
    {
        int tot=0,b=0;
        for(int j=1;j<=num;j++)tot+=dp[i-1][j],tot%=mod;//区间总和
        for(int j=1;j<=min(num,1+t-2);j++)b+=dp[i-1][j],b%=mod;//相当于初始区间，从1开始，取min是防止t>n
        for(int j=1;j<=num;j++)
        {
            if(j+t-1<=num)//防止越界
                b+=dp[i-1][j+t-1],b=(b)%mod;
            if(j-t>=1)//防止越界
                b-=dp[i-1][j-t],b=(b+mod)%mod;//防止对负数取模
            if(vis[j])//是否存在
                dp[i][j]=(dp[i][j]+tot-b+mod)%mod;//防止对负数取模
        }
    }
    int ans=0;
    for(int i=1;i<=num;i++)
        ans=(ans+dp[n][i])%mod;
    cout<<ans<<endl;
    return 0;
}