題目鏈接：點(diǎn)擊查看

題目大意：

給了你一個(gè)極端大的數(shù)據(jù)集合的信息
N, SUM, X 如下

這個(gè)數(shù)據(jù)集合里面的N位, 每一數(shù)位求和之后剛好等于SUM （比如四位數(shù) 1234 數(shù)位求和之后是 10）;

它們都有N位, 十進(jìn)制的(每一位都在0~9), 我們這里降低點(diǎn)難度, 特別容許前導(dǎo)0的存在. 1234, 0123 都是合理的數(shù);

這N位長(zhǎng)度的數(shù)字字符串, 任意連續(xù)的三位數(shù)字構(gòu)成的數(shù)據(jù)都能被X整除.

PS: 有可能 有空數(shù)據(jù)集

為了減低難度你只要求出原來(lái)數(shù)據(jù)集合內(nèi)有多少數(shù)據(jù) mod 1000009 就好

題目分析：對(duì)數(shù)位dp不敏感，比賽的時(shí)候讀完這個(gè)題一點(diǎn)思路都沒(méi)有，賽后看了一眼別人代碼就恍然大悟，這個(gè)題目與其說(shuō)是數(shù)位dp，不如說(shuō)是記憶化搜索，因?yàn)轭}目允許存在前導(dǎo)零，也就不用 limit 變量進(jìn)行約束，從而實(shí)現(xiàn)就簡(jiǎn)單了好多好多

套上模板就好了，有個(gè)點(diǎn)需要注意的是，dp數(shù)組需要開(kāi) int ，如果開(kāi) long long 的話會(huì)爆內(nèi)存

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;const int mod=1000009;int dp[55][4505][15][15];//dp[pos][sum][pre1][pre2]int b[55],s,x,n;LL dfs(int pos,int sum,int pre1,int pre2) {if(pos==-1)return sum==s;if(dp[pos][sum][pre1][pre2]!=-1)return dp[pos][sum][pre1][pre2];int ans=0;for(int i=0;i<=9;i++){if(pre1!=-1&&pre2!=-1&&(pre1*100+pre2*10+i)%x)continue;ans=(ans+dfs(pos-1,sum+i,pre2,i))%mod;}dp[pos][sum][pre1][pre2]=ans;return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);memset(dp,-1,sizeof(dp));scanf("%d%d%d",&n,&s,&x);cout<<dfs(n-1,0,-1,-1)<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客 - 数位操作2(数位dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。