[bzoj1833]-[ZJOI2010]count数字计数

发布于 2018-03-14  108 次阅读



题目(BZOJ) 小心PE~
题目(洛谷)
 
设dp[pos][num][sum]表示当前位为pos,要查找的数为num,之前有sum位是num,然后就是裸数位dp了......

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
ll L,R;
ll dp[15][10][15];
int n,b[15];
ll dfs(int pos,int num,int sum,bool lead,bool lim){
	if(!pos)return sum;
	if(!lim&&!lead&&dp[pos][num][sum]!=-1)return dp[pos][num][sum];
	int up=lim?b[pos]:9;
	ll ret=0;
	if(!lead||pos==1)ret+=dfs(pos-1,num,sum+(num==0),0,lim&&up==0);
	else ret+=dfs(pos-1,num,sum,1,lim&&up==0);
	for(int i=1;i<=up;++i){
		ret+=dfs(pos-1,num,sum+(num==i),0,lim&&i==up);
	}
	if(!lim&&!lead)dp[pos][num][sum]=ret;
	return ret;
}
inline ll solve(ll x,ll i){
	n=0;while(x)b[++n]=
	if(!n)b[++n]=0;
	memset(dp,-1,sizeof dp);
	return dfs(n,i,0,1,1);
}
int main(){
	read(L),read(R);
	for(int i=0;i<=8;++i)
		printf(
	printf(
	return 0;
}