数位dp两题(洛谷/BZOJ)
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;
} 
投递美团等公司10个岗位 >
你cet6就cet6，cet4就cet4，你写个cet证书等是什么意思。专业技能快赶上项目行数，你做的这2个项目哪里能提现你有这么多技能呢
。管你学多少，电子科大的bg就注定了你我的命运不同