推荐以下一篇博客：https://blog.csdn.net/wust_zzwh/article/details/52100392
1.(HDOJ2089)http://acm.hdu.edu.cn/showproblem.php?pid=2089
分析：裸模板题
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[];
int dp[][];
int dfs(int pos,int pre,int sta,bool limit)
{
if ( pos==- ) return ;
if ( !limit && dp[pos][sta]!=- ) return dp[pos][sta];
int up=limit?a[pos]:;
int tmp=;
for ( int i=;i<=up;i++ )
{
if ( pre== && i== ) continue;
if ( i== ) continue;
tmp+=dfs(pos-,i,i==,limit&&i==a[pos]);
}
if ( !limit ) dp[pos][sta]=tmp;
return tmp;
} int solve(int x)
{
int pos=;
while ( x )
{
a[pos++]=x%;
x/=;
}
return dfs(pos-,-,,true);
} int main()
{
int l,r;
while ( scanf("%d%d",&l,&r)!=EOF && (l+r) )
{
memset(dp,-,sizeof(dp));
printf("%d\n",solve(r)-solve(l-));
}
return ;
}
HDOJ2089
2.(HDOJ3555)http://acm.hdu.edu.cn/showproblem.php?pid=3555
题意：求区间内不出现49的数的个数
分析：裸模板题
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[];
ll dp[][];
ll dfs(int pos,int pre,int sta,bool limit)
{
if ( pos==- ) return ;
if ( !limit && dp[pos][sta]!=- ) return dp[pos][sta];
int up=limit?a[pos]:;
ll tmp=;
for ( int i=;i<=up;i++ )
{
if ( pre== && i== ) continue;
tmp+=dfs(pos-,i,i==,limit&&i==a[pos]);
}
if ( !limit ) dp[pos][sta]=tmp;
return tmp;
} ll solve(ll x)
{
int pos=;
while ( x )
{
a[pos++]=x%;
x/=;
}
return dfs(pos-,-,,true);
} int main()
{
ll l,r,T;
memset(dp,-,sizeof(dp));
scanf("%lld",&T);
while ( T-- )
{
scanf("%lld",&r);
printf("%lld\n",r-solve(r)+);
}
return ;
}
HDOJ3555
3.(HDOJ4734)http://acm.hdu.edu.cn/showproblem.php?pid=4734
题意：题目给了个f(x)的定义：F(x) = An * 2n-1 + An-1 * 2n-2 + … + A2 * 2 + A1 * 1，Ai是十进制数位，然后给出a,b求区间[0,b]内满足f(i)<=f(a)的i的个数。
分析：采用相减的思想,dp[i][j]，第一维表示处于数字的第几位（即pos），第二维表示是枚举到当前pos位，后面位数最多能凑的权值和为j（起始值为f(a)），最后当j>=0是满足条件的数。具体解释见上面的博客
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;
int a[];
int dp[][maxn];
int sum;
int pow_[maxn]; int dfs(int pos,int sta,bool limit)
{
if ( pos==- ) return ;
if ( !limit && dp[pos][sta]!=- ) return dp[pos][sta];
int up=limit?a[pos]:;
int tmp=;
for ( int i=;i<=up;i++ )
{
int x=pow_[pos]*i;
if ( sta-x< ) continue;
tmp+=dfs(pos-,sta-x,limit&&i==a[pos]);
}
if ( !limit ) dp[pos][sta]=tmp;
return tmp;
} int solve(int x)
{
int pos=;
while ( x )
{
a[pos++]=x%;
x/=;
}
return dfs(pos-,sum,true);
} int main()
{
int l,r,T,i,j,k,h,A,B,x,y,z,cnt;
pow_[]=;
for ( i=;i<=;i++ ) pow_[i]=pow_[i-]*;
scanf("%d",&T);
memset(dp,-,sizeof(dp));
for ( h=;h<=T;h++ )
{
scanf("%d%d",&A,&B);
sum=;
cnt=;
x=A;
while ( x )
{
y=x%;
sum+=y*pow_[cnt++];
x/=;
}
printf("Case #%d: %d\n",h,solve(B));
}
return ;
}
HDOJ4734
4.(POJ3252)http://poj.org/problem?id=3252
题意：求一个范围内满足，二进制下0的位数>=1的位数的个数
分析：将原先的十进制一位转化为二进制一位.此题要在dfs中添加bool型的lead表示前导0，因为这题需要拿0的个数和1的个数比较，所以需要考虑前导0.同时dp数组的第二维记录的是0的个数-1的个数。因为可能为负，所以初始值不为0，而记一个较大的数（我记的是32，只要能使得过程不为负即可）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[];
ll dp[][];
ll dfs(int pos,int sta,bool lead,bool limit)
{
if ( pos==- ) return sta>=;
if ( !limit && !lead && dp[pos][sta]!=- ) return dp[pos][sta];
int up=limit?a[pos]:;
ll tmp=;
for ( int i=;i<=up;i++ )
{
if(lead && i==) tmp+=dfs(pos-,sta,lead,limit && i==a[pos]);
else tmp+=dfs(pos-,sta+(i==?:-),lead && i==,limit && i==a[pos]);
}
if ( !limit&&!lead ) dp[pos][sta]=tmp;
return tmp;
} ll solve(ll x)
{
int pos=;
while ( x )
{
a[pos++]=x%;
x/=;
}
return dfs(pos-,,true,true);
} int main()
{
ll l,r;
memset(dp,-,sizeof(dp));
while ( scanf("%lld%lld",&l,&r)!=EOF )
{
printf("%lld\n",solve(r)-solve(l-));
}
return ;
}
POJ3252
5.(HDOJ5179)http://acm.hdu.edu.cn/showproblem.php?pid=5179
题意：给定一个数A,a数组从0开始对应着数A从左到右的每一尾，现在要求数A右边的数都不比左边的数大，同时要求在左边的数去模右边的数都为0
分析：dp数组的第二维记录前一位数是多少即可。转移时要转移到比前一位数小的数同时要被前一位数取模为0的数
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[];
int dp[][];
int dfs(int pos,int sta,bool lead,bool limit)
{
if ( pos==- ) return ;
if ( !limit && !lead && dp[pos][sta]!=- ) return dp[pos][sta];
int up=limit?a[pos]:;
int tmp=;
for ( int i=;i<=up;i++ )
{
if ( !lead&&i== ) continue;
if ( lead )
{
tmp+=dfs(pos-,i,lead && i==,limit&&i==a[pos]);
continue;
}
if ( i>sta&&sta!=- ) break;
if ( sta%i!= && sta!=- ) continue;
tmp+=dfs(pos-,i,lead && i==,limit&&i==a[pos]);
}
if ( !limit&&!lead ) dp[pos][sta]=tmp;
return tmp;
} int solve(int x)
{
int pos=;
while ( x )
{
a[pos++]=x%;
x/=;
}
return dfs(pos-,-,true,true);
} int main()
{
int l,r,T;
scanf("%d",&T);
memset(dp,-,sizeof(dp));
while ( T-- )
{
scanf("%d%d",&l,&r);
printf("%d\n",solve(r)-solve(l-));
}
return ;
}
HDOJ5179
6.（HDOJ3652）http://acm.hdu.edu.cn/showproblem.php?pid=3652
题意：给定一个范围，求该范围内不含13同时不是13倍数的数的个数
分析：设置三维数组dp[i][j][k]，第一维表示位置，第二维表示13的余数，
第三维有三个值，0代表此前还未出现过13同时前一位不为1，1代表此前还未出现过13同时前1位位1，2代表此前已经出现过了13
最后判断时，只有当第二维为0，第三维为2时才加入计数
注意第三维转移时到底是多少
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[];
int dp[][][];
int dfs(int pos,int rem,int sta,bool limit)
{
if ( pos==- ) return rem==&&sta==;
if ( !limit && dp[pos][rem][sta]!=- ) return dp[pos][rem][sta];
int up=limit?a[pos]:;
int tmp=;
for ( int i=;i<=up;i++ )
{
int x=sta;
if ( sta== && i== ) x=;
if ( sta== && i!= ) x=;
if ( sta== && i== ) x=;
tmp+=dfs(pos-,(rem*+i)%,x,limit&&i==a[pos]);
}
if ( !limit ) dp[pos][rem][sta]=tmp;
return tmp;
} int solve(int x)
{
int pos=;
while ( x )
{
a[pos++]=x%;
x/=;
}
return dfs(pos-,,,true);
} int main()
{
int l,r;
memset(dp,-,sizeof(dp));
while ( scanf("%d",&r)!=EOF )
{
printf("%d\n",solve(r));
}
return ;
}
HDOJ3652
7.（HDOJ3709）http://acm.hdu.edu.cn/showproblem.php?pid=3709
题意：求区间[L, R]内平衡数的个数 平衡数的定义是指，以某位作为支点，此位的左面（数字 * 距离）之和 与右边相等,距离是指某位到支点的距离;
分析：首先需要明确一个数如果是平衡数，那么它的支点一定是确定。所以需要枚举支点是哪个点。要注意在数位dp的dfs中，由于 0 对于每个位置都会被统计到，最后要再减去重复的。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[];
ll dp[][][];
ll dfs(int pos,int bal,int sum,bool limit)
{
if ( pos==- ) return sum==;
if ( !limit && dp[pos][bal][sum]!=- ) return dp[pos][bal][sum];
int up=limit?a[pos]:;
ll tmp=;
for ( int i=;i<=up;i++ )
{
if ( sum+(pos-bal)*i< ) continue;
tmp+=dfs(pos-,bal,sum+(pos-bal)*i,limit&&i==a[pos]);
}
if ( !limit ) dp[pos][bal][sum]=tmp;
return tmp;
} ll solve(ll x)
{
if ( x==- ) return ;
int pos=;
while ( x )
{
a[pos++]=x%;
x/=;
}
ll ans=;
for ( int i=;i<pos;i++ ) ans+=dfs(pos-,i,,true);
return ans-pos+;
} int main()
{
ll l,r;
int T;
memset(dp,-,sizeof(dp));
scanf("%d",&T);
while ( T-- )
{
scanf("%I64d%I64d",&l,&r);
printf("%I64d\n",solve(r)-solve(l-));
}
return ;
}
HDOJ3709
8.（HDOJ4507）http://acm.hdu.edu.cn/showproblem.php?pid=4507
分析：dp[i][j][k]第二维表示%7后的余数，第三维表示所有位数的和%7后的值。因为要求的是所有满足条件的数的平方和，我们考虑对一个数按平方和规则进行拆分。
结构体数组dp中记录三个值,cnt代表满足条件的数的个数，sum表示满足条件的数的求和，sum2表示满足条件的数的平方和.
以下转移式为不带取模的转移方程,假设第i位是当前这位,pos为当前所处的位置,p[pos]代表10^pos次，当前的状态为ans，子状态为tmp(方法：先考虑单个式子再进行累加)
ans.cnt+=tmp.cnt
ans.sum+=(tmp.sum+tmp.cnt*(i*p[pos]))
ans.sum2+=(tmp.cnt*（(i*p[pos])^2）+2*(i*p[i])*tmp.sum+tmp.sum2)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+;
int a[];
ll p[];
struct node{
ll cnt,sum,sum2;
node(ll _cnt=,ll _sum=,ll _sum2=):cnt(_cnt),sum(_sum),sum2(_sum2) {}
}dp[][][]; node dfs(int pos,int rem,int snum,bool limit)
{
if ( pos==- )
{
node ss(,,);
if ( rem!= && snum!= ) ss.cnt=;
return ss;
}
if ( !limit && dp[pos][rem][snum].sum2!=- ) return dp[pos][rem][snum];
int up=limit?a[pos]:;
node ans(,,);
for ( int i=;i<=up;i++ )
{
if ( i== ) continue;
node tmp=dfs(pos-,(rem*+i)%,(snum+i)%,limit&&i==a[pos]);
ans.cnt+=tmp.cnt;
ans.cnt%=mod;
ans.sum+=(tmp.sum+i*p[pos]%mod*tmp.cnt%mod)%mod;
ans.sum%=mod;
ans.sum2+=(tmp.sum2+*p[pos]*i%mod*tmp.sum%mod)%mod;
ans.sum2%=mod;
ans.sum2+=(tmp.cnt*p[pos]%mod*p[pos]%mod*i*i%mod);
ans.sum2%=mod;
}
if ( !limit ) dp[pos][rem][snum]=ans;
return ans;
} ll solve(ll x)
{
int pos=;
while ( x )
{
a[pos++]=x%;
x/=;
}
node tmp=dfs(pos-,,,true);
return tmp.sum2;
} int main()
{
ll l,r;
int T;
memset(dp,-,sizeof(dp));
p[]=;
for ( int i=;i<=;i++ ) p[i]=(p[i-]*)%mod;
scanf("%d",&T);
while ( T-- )
{
scanf("%I64d%I64d",&l,&r);
printf("%I64d\n",((solve(r)-solve(l-))%mod+mod)%mod);
}
return ;
}
HDOJ4507
9.（HDOJ3886）http://acm.hdu.edu.cn/showproblem.php?pid=3886
题意：给出一个字符，只含’/’，’-‘ ，’\’ ，表示着一个数上的各位数字按相应字符上升，不变或下降，问【a,b】区间内这样的数有多少个？
分析;dp[i][j][k]第二维表示前一个值是什么，第三维表示当前处于波动字符串的第几个位置
要注意几点：
a、为了确保每个数只被计算一次，当能进入一个新的起伏时，尽量先进入，如果不能再判断是否符合之前的起伏。
b、前导零不应该被算入起伏中，起伏只能在没有前导零的数中匹配。
c、n个运算符至少要有n+1个数。
d、注意开始的状态，第一个数以及第一个运算符。
e、注意大数减一的计算。
f、注意减法的取模。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;
const int mod=1e8;
char s1[maxn],s2[maxn],op[maxn];
int a[maxn];
int dp[maxn][][maxn],len; bool check ( int x , int y , char c )
{
if ( c == '/' && x < y ) return true ;
if ( c == '-' && x == y ) return true ;
if ( c == '\\' && x > y ) return true ;
return false ;
} ll dfs(int pos,int pre,int p,bool lead,bool limit)
{
if ( pos==- ) return p==len;
if ( !limit && !lead && dp[pos][pre][p]!=- ) return dp[pos][pre][p];
int up=limit?a[pos]:;
ll tmp=;
for ( int i=;i<=up;i++ )
{ if ( lead ) tmp=(tmp+dfs(pos-,i,p,lead&&i==,limit&&i==a[pos]))%mod;
else if ( p<len && check(pre,i,op[p+]) ) tmp=(tmp+dfs(pos-,i,p+,lead,limit&&i==a[pos]))%mod;
else if ( p> && check(pre,i,op[p]) ) tmp=(tmp+dfs(pos-,i,p,lead,limit&&i==a[pos]))%mod;
}
if ( !limit&&!lead ) dp[pos][pre][p]=tmp%mod;
return tmp;
} ll solve(char *x,int f)
{
int i=,pos=;
int len_=strlen(x);
while ( x[i]=='' ) i++;
if ( x[i]=='\0' ) return ;
for( int j=len_-;j>=i;j-- ) a[pos++]=x[j]-'';
if( f )
{
a[]--;
for( int j=;j<pos;j++ )
{
if(a[j]<)
{
a[j]+=;
a[j+]--;
}
}
}
pos--;
if( a[pos]== ) pos--;
return dfs(pos,,,true,true)%mod;
} int main()
{
int l,r;
while ( scanf("%s",op+)!=EOF )
{
memset(dp,-,sizeof(dp));
len=strlen(op+);
scanf("%s%s",s1,s2);
ll r=solve(s2,);
ll l=solve(s1,);
printf("%08lld\n",(r-l+mod)%mod);
}
return ;
}
HDOJ3886
10.(HDOJ4352)http://acm.hdu.edu.cn/showproblem.php?pid=4352
题意：给定一个区间，让你求这个区间中数位从左到右满足LIS恰好为m的数的个数
分析：dp[i][j][k],第二维表示当前的状态（即LIS），第三维表示所求的LIS的长度
第二维中要用到LIS的nlogn的算法,具体见https://blog.csdn.net/shuangde800/article/details/7474903。 大致的含义就是j的二进制表示下有多少个位置为1代表LIS的长度为多少，从小到大出现的第i个1的位置j代表长度为i的LIS结尾为j。每次更新时，不断更新j(大致思想就是nlogn的LIS做法),注意记忆化返回的是要求的LIS长度的状态，而不是当前状态的LIS长度的状态
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[],m;
ll dp[][][]; int getnews(int x,int s)
{
for( int i=x;i<=;i++ )
if(s&(<<i)) return (s^(<<i))|(<<x);
return s|(<<x);
} int count(int x)
{
int cnt=;
while ( x )
{
if ( x& ) cnt++;
x/=;
}
return cnt;
} ll dfs(int pos,int sta,bool lead,bool limit)
{
if ( pos==- ) return count(sta)==m;
if ( !limit && !lead && dp[pos][sta][m]!=- ) return dp[pos][sta][m];
int up=limit?a[pos]:;
ll tmp=;
for ( int i=;i<=up;i++ )
{
tmp+=dfs(pos-,(lead&&i==)?:getnews(i,sta),lead&&i==,limit&&i==a[pos]);
}
if ( !limit&&!lead ) dp[pos][sta][m]=tmp;
return tmp;
} ll solve(ll x)
{
int pos=;
while ( x )
{
a[pos++]=x%;
x/=;
}
return dfs(pos-,,true,true);
} int main()
{
ll l,r;
int T,h;
memset(dp,-,sizeof(dp));
scanf("%d",&T);
for ( h=;h<=T;h++ )
{
scanf("%lld%lld%d",&l,&r,&m);
printf("Case #%d: %lld\n",h,solve(r)-solve(l-));
}
return ;
}
HDOJ4352
