題目鏈接：點擊查看

題目大意：求a到b閉區(qū)間內(nèi)滿足相鄰兩個數(shù)字之差大于等于2的數(shù)字個數(shù)

分析：dp[i][j]表示第i位上數(shù)字為j的結(jié)果，pos表示位數(shù)，pre表示上一位數(shù)，lead表示是否有前導0，limit表示是否為最高位

代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=30;LL dp[20][10];int b[N];LL dfs(int pos,int pre,bool lead,bool limit) {if(pos==-1)return 1;if(!limit&&dp[pos][pre]!=-1&&pre>0)//pre>0，如果pre==0，涉及到位數(shù)，需要再次循環(huán)return dp[pos][pre];int up=limit?b[pos]:9;LL ans=0;for(int i=0;i<=up;i++){if(abs(i-pre)>=2||lead)ans+=dfs(pos-1,i,lead&&(i==0),limit&&(i==b[pos]));}if(!limit)dp[pos][pre]=ans;return ans; }LL solve(LL n) {int cnt=0;while(n){b[cnt++]=n%10;n/=10;}return dfs(cnt-1,-1,true,true); }int main() { // freopen("input.txt","r",stdin);LL a,b;memset(dp,-1,sizeof(dp));while(cin>>a>>b){cout<<solve(b)-solve(a-1)<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HYSBZ - 1026 windy数(数位dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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