CF1498C

发表于 | 分类于 |

题面:https://codeforces.com/problemset/problem/1498/C

大致题意：给定n块板子，在第一块板子的左方发射一个初始值为D(k)的粒子，规则是粒子每穿过一个板子，自身D(k)值不变，若k>1则会分裂出一个新的D(k-1)的粒子，方向相反，求产生的粒子总数

题解：很明显是要用动态规划，但状态转移方程有点难想，若用dp[i][k][j]表示D(k)粒子从j(1表示从左向右，0表示从右向左)方向撞向第i个板子所产生的粒子总数，则dp[i][k][1]=dp[i-1][k-1][0]+dp[i+1][k][1],dp[i][k][0]=dp[i+1][k-1][1]+dp[i-1][k][0];dp[i][1][j]都初始化成1(注意首尾板子要特判)

使用记忆化dfs时间复杂度为O(2nk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<stack>
#include<unordered_set>
using namespace std;
using ll = int64_t;
const ll mod = 1e9 + 7;
ll T, n, m, k;
ll tmp, dp[1005][1005][2];
ll dfs(ll i,ll k,ll j)
{
    if(k==1)
    {
        return 1;
    }
    if(dp[i][k][j]!=-1)
    {
        return dp[i][k][j];
    }
    ll ans = 2;
    if(j==1)
    {
        if(i!=1)
        {
            
            ans += dfs(i - 1, k - 1, 0)-1;
            ans %= mod;
        }
        if(i!=n)
        {
            ans += dfs(i + 1, k, 1)-1;
            ans %= mod;
        }   
    }
    if(j==0)
    {
        if(i!=n)
        {
            ans += dfs(i + 1, k - 1, 1) - 1;
            ans %= mod;
        }
        if(i!=1)
        {
            ans += dfs(i - 1, k, 0)-1;
            ans %= mod;
        }
        
    }
    return dp[i][k][j] = ans%mod;
}
int main()
{
    T = 1;
    cin >> T;
    while(T--)
    {
            cin >> n >> k;
            for (ll i = 1; i <= n;i++)
            {
                for (ll j = 2; j <= k;j++)
                {
                    dp[i][j][1] = -1;
                    dp[i][j][0] = -1;
                }
                dp[i][1][1] = 1;
                dp[i][1][0] = 1;
            }
            cout << (dfs(1, k, 1)+mod)%mod << "\n";
    }
    return 0;
}