Balanced Number 数位dp

题意：　　给出求ab之间有多少个平衡数   4139为平衡数   以3为轴   1*1 4*2==9*1 

 

思路很好想但是一直wa  ：

注意要减去前导零的情况 0 00 000 0000   不能反复计算

#include<bits/stdc  .h>using namespace std;//input by bxd#define rep(i,a,b) for(int i=(a);i<=(b);i  )#define repp(i,a,b) for(int i=(a);i>=(b);--i)#define RI(n) scanf("%d",&(n))#define RII(n,m) scanf("%d%d",&n,&m)#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)#define RS(s) scanf("%s",s);#define ll long long#define REP(i,N)  for(int i=0;i<(N);i  )#define CLR(A,v)  memset(A,v,sizeof A)//////////////////////////////////#define inf 0x3f3f3f3f#define N 3700 5#define MID N/2ll dp[20][20][N];ll a[20];ll dfs(int pos,int t,int state,bool lead,bool limit  ){    if(!pos)return state==0;    if(!limit&&!lead&&dp[pos][t][state MID]!=-1)return dp[pos][t][state MID];    ll ans=0;    int up=limit?a[pos]:9;    rep(i,0,up)    {        ans =dfs(pos-1,t,state i*(pos-t), lead&&i==0,limit&&i==a[pos]);    }    if(!limit&&!lead)dp[pos][t][state MID]=ans;    return ans;}ll solve(ll x){    int pos=0;    ll ans=0;    while(x)    {        a[  pos]=x;        x/=10;    }    rep(i,1,pos)    ans =dfs(pos,i,0,true,true);    return ans-pos 1;//去除前导零}int main(){    int cas;    CLR(dp,-1);    RI(cas);    while(cas--)    {        ll a,b;        cin>>a>>b;        printf("%lld\n",solve(b)-solve(a-1));    }    return 0;}

View Code

 

或者

#include<bits/stdc  .h>using namespace std;//input by bxd#define rep(i,a,b) for(int i=(a);i<=(b);i  )#define repp(i,a,b) for(int i=(a);i>=(b);--i)#define RI(n) scanf("%d",&(n))#define RII(n,m) scanf("%d%d",&n,&m)#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)#define RS(s) scanf("%s",s);#define ll long long#define REP(i,N)  for(int i=0;i<(N);i  )#define CLR(A,v)  memset(A,v,sizeof A)//////////////////////////////////#define inf 0x3f3f3f3f#define N 3700 5#define MID N/2ll dp[20][20][N];ll a[20];ll dfs(int pos,int t,int state,bool lead,bool limit  ){    if(!pos)return !lead&&state==0;    if(!limit&&!lead&&dp[pos][t][state MID]!=-1)return dp[pos][t][state MID];    ll ans=0;    int up=limit?a[pos]:9;    rep(i,0,up)    {        ans =dfs(pos-1,t,state i*(pos-t), lead&&i==0,limit&&i==a[pos]);    }    if(!limit&&!lead)dp[pos][t][state MID]=ans;    return ans;}ll solve(ll x){    if(x<0)return 0;    if(x==0)return 1;    int pos=0;    ll ans=0;    while(x)    {        a[  pos]=x;        x/=10;    }    rep(i,1,pos)    ans =dfs(pos,i,0,true,true);    return ans 1;//去除前导零}int main(){    int cas;    CLR(dp,-1);    RI(cas);    while(cas--)    {        ll a,b;        cin>>a>>b;        printf("%lld\n",solve(b)-solve(a-1));    }    return 0;}

View Code

 

来源：http://www.icode9.com/content-4-165851.html