题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6787

在这里插入图片描述

思路

设dp[i][j]表示到达位置 i 时,已经放了 j 个传送门。
初始时,只要j=0,则dp[i][j]=1;
其余情况用k表示在位置i之前有多少个连续的传送门,因为题目说的是 "有可能" 能到终点,那么当k<=10,一定可以实现两点之间的转移,在这两点之间是k个连续的传送门,每个传送门选择传送到的位置可以是其前面的所有位置。每个dp[i][j]累加上k=0,1,2...10的所有方案,则方程为:
$①k=0, dp[i][j]+=dp[i-1][j]$
$②k∈[1,10], dp[i][j]+=dp[i-k-1][j-k]{(i-k-1)(i-k-2)...(i-2)}$

AC代码

//1216MS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10,mod=1e9+7;
int T,n,m;
ll dp[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        if(m>n-2&&n>12) // n>12不要漏掉
        {
            printf("-1\n");
            continue;
        }
        if(m==0)
        {
            printf("1\n");
            continue;
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            dp[i][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                ll s=1;
                dp[i][j]+=dp[i-1][j]; // k=0
                for(int k=1;k<=10&&i-k-1>=1&&j-k>=0;k++)
                {
                    s=s*(i-k-1)%mod;
                    dp[i][j]=(dp[i][j]+dp[i-k-1][j-k]*s%mod)%mod;
                }
            }
        }
        if(dp[n][m]==0) printf("-1\n");
        else printf("%lld\n",dp[n][m]);
    }
    return 0;
}
/*
2
13 11
14 11
ans:
-1
967524480
*/

改进后的 AC代码

按上面代码那么写,多组数据,每次都要打表,比较耗时间,建议先打表预处理,之后可以直接O(1)回答每次询问,时间复杂度$O(n^2+T)$。

//109MS 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3,mod=1e9+7;
int T,n,m;
ll dp[N+10][N+10];
int main()
{
    ios::sync_with_stdio(false);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=N;i++)
        dp[i][0]=1;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            ll s=1;
            dp[i][j]+=dp[i-1][j]; // k=0
            for(int k=1;k<=10&&i-k-1>=1&&j-k>=0;k++)
            {
                s=s*(i-k-1)%mod;
                dp[i][j]=(dp[i][j]+dp[i-k-1][j-k]*s%mod)%mod;
            }
        }
    }
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        if(dp[n][m]==0)printf("-1\n");
        else printf("%lld\n",dp[n][m]);
    }
    return 0;
}