HDU 6787 Chess（线性动态规划）

这题是2020百度之星初赛第三场1005
题意描述
一个长度为n的棋盘（$1\leq n\leq1000$），恰好放置m个传送门（$0\leq m\leq1000$），传送门可以向之前的任意一点传送且如传送到的位置有传送门可连续传送，每次选手投掷骰子可以掷出1~11，即如果当前在位置 y 且投出数字 x，那棋子将会跳到位置 y+x。问有多少种设置棋盘的方式可以让选手从起点1走到终点n？

题目分析
1.起点1和终点n不能放置传送门
2.当前位置x放置传送门可传送到1~x-1位置，共x-1种传送门
3.因为掷骰子最大为11，连续放置传送门数量最大为10。
4.若传送门放不下，则输出-1。比如样例23 21，长度为23的棋盘最大放置20个传送门OXXXXXXXXXXOXXXXXXXXXXO，就像这样。

解题思路
1.简化问题第一步，当没有传送门时，问题转化为上楼梯问题，求方案数。动态转移方程：$dp[i]=dp[i-1]+dp[i-2]+...+dp[i-11];$
2.简化问题第二步，当传送门随意放置时，仅变化动态转移方程：
$dp[i]=dp[i-1];$
$dp[i]=dp[i]+dp[i-2]*(i-2)+...dp[x]*\frac{(i-2)!}{(i-x-1)!}...+dp[i-11]*\frac{(i-2)!}{(i-12)!};$
3.问题求解，$dp[当前位置][已放置传送门数量]$，当走到位置i时，已放置j个传送门时，动态转移方程：
$dp[i][j]=dp[i-1][j];$
$dp[i][j]=dp[i][j]+dp[i-2][j-1]*(i-2)+...dp[x][j-(i-x-1)]*\frac{(i-2)!}{(i-x-1)!}...+dp[i-11][j-10]*\frac{(i-2)!}{(i-12)!};$
这里注意为了避免重复计算，在计算中间不放置传送门时，只能从前一个位置转移方案数过来（这里并不会漏计算，从x到y，一格一格跳过来和从x直接跳到y方案数是一样的）。
而中间如果放置传送门时，从x到y，中间必须放满传送门，方案数用“x位置的方案数*中间每个位置能放置传送门的种类数”，注意要从x位置减去中间放置传送门数的那种方案来乘，也就是要从$dp[x][j-(y-x-1)]$位置转移。
4.注意无解情况，最多放置传送门需要让两个能走的位置中间不超过10个，用公式判断$(m+(m-1)/10>n-2)$。

附赠奇怪样例
input1

3
1 0
23 20
23 21
23 1000

output1

1
6622482
-1
-1

input2

5
5 0
5 1
5 2
5 3
5 4

output2

1
6
11
6
-1

input3

6
6 0
6 1
6 2
6 3
6 4
6 5

output3

1
10
35
50
24
-1

感谢胡同学写的暴力帮我找到WA点

#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stack>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#define eps 0.00000001
#define pi P_MI
#define ll long long
using namespace std;
struct point {
    int x,y;
    bool operator < (const point &a) const {
        return x>a.x;//最小值优先
    }
};

priority_queue <int> que;

ll a[1100][1100];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(a,0,sizeof(a));
        if (m+(m-1)/10>n-2){
            if (n==1 && m==0) printf("1\n");
            else printf("-1\n");
            continue;
        }
        a[1][0]=1;
        m=min(m,max(n-2,0));
        for (int i=2; i<=n; i++) {
            int mm=min(i-2,m);
            for (int j=0; j<=mm; j++) {
                a[i][j] = a[i-1][j];

                for (int k= max( i-j-1, max(1,i-11) ); k<=i-2; k++) {
                    ll sum=1;
                    for (ll l=k; l<=i-2; l++){
                        sum = sum * l % 1000000007;
                    }
                    a[i][j] = (a[i][j] + sum*a[k][j-(i-k-1)]) % 1000000007;
                }

            }
        }
        a[n][m]=a[n][m]%1000000007;
        printf("%lld\n",a[n][m]);
    }
    return 0;
}
//    freopen("1.in","r",stdin);
//    freopen("1.out","w",stdout);

本文地址：https://blog.csdn.net/aiaidexiaji/article/details/107603516