文章

7

粉丝

387

获赞

7

访问

67.5k

头像
数位DP+记忆化搜索模板题目
P1421 清华大学机试题
发布于2021年1月11日 19:42
阅读数 9.4k

主要是注意高精度,这样的话连续出现某一个数的状态计数就要更多

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod = 20123;
int s[105];
//pos num sta
ll dp[105][30][105];
//dfs参数:当前数位,当前状态,是否是开头,是否有最高位的限制,要求出现次数的数字
ll dfs(int pos, int sta, int lead, int limit, int number) {
    if(pos == -1) return sta % mod;
    if(!limit && !lead && dp[pos][number][sta] != -1)
        return dp[pos][number][sta] % mod;
    ll ret = 0;
    int up = limit ? s[pos] : 9;//无限制则最高可以冲到9
    for(int i = 0; i <= up; ++i) {
        if(lead == 1 && i == 0)
            ret = (ret + dfs(pos - 1, sta, lead, limit && (i == up), number)) % mod;
        else
            ret = (ret + dfs(pos - 1, sta + (number == i), lead && i == 0, limit && (i == up), number)) % mod;
    }
    if(!limit && !lead) dp[pos][number][sta] = ret % mod;
    return ret % mod;
}
//[1, ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发