P2657 [SCOI2009]windy数
code :
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[15][15]; int a[15],len; ll dfs(int pos,int pre,int lead,int limit) { if(pos>len) return 1; if(!limit&&dp[pos][pre]!=-1) return dp[pos][pre]; int up=limit?a[len-pos+1]:9; ll ans=0; for(int i=0;i<=up;i++) { if(abs(i-pre)<2) continue; if(lead&&i==0) ans+=dfs(pos+1,-2,1,limit&&i==up); else ans+=dfs(pos+1,i,0,limit&&i==up); } return (!limit&&!lead)?(dp[pos][pre]=ans):ans; } ll cal(ll x) { len=0; memset(dp,-1,sizeof(dp)); while(x) { a[++len]=x%10; x/=10; } return dfs(1,-2,1,1); } int main() { ll l,r; cin>>l>>r; cout<<cal(r)-cal(l-1); return 0; }
P2602 [ZJOI2010]数字计数
code :
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[15][15]; int a[15],len; ll dfs(int pos,ll cnt,int dig,int lead,int limit) { if(pos>len) return cnt; if(!lead&&!limit&&dp[pos][cnt]!=-1) return dp[pos][cnt]; int up=limit?a[len-pos+1]:9; ll ans=0; for(int i=0;i<=up;i++) ans+=dfs(pos+1,cnt+((i||lead==0)&&i==dig),dig,!i&&lead,limit&&i==up); return (!limit&&!lead)?(dp[pos][cnt]=ans):ans; } ll cal(ll x,int i) { len=0; memset(dp,-1,sizeof(dp)); while(x) { a[++len]=x%10; x/=10; } return dfs(1,(ll)0,i,1,1); } int main() { ll l,r; cin>>l>>r; for(int i=0;i<=9;i++) cout<<cal(r,i)-cal(l-1,i)<<" "; return 0; }