BZOJ 2063: 我爸是李刚

2063: 我爸是李刚

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 155 Solved: 82
[Submit][Status][Discuss]

Description

背景： LC同学在2011年的浙江省选中轻松虐爆了WJMZBMR，无压力进入省队并参加了NOI 2011，在1个小时之后，A光了所有题目的LC同学轻松的喝着茶，哼着小曲。由于在信息学方面的杰出表现以及LC同学的父亲是伟大的LG同志。 LC同学轻松获得了2012年诺亚方舟的船票。并且得到了卖票员这一肥差。题目描述：卖票员这一工作十分简单，世界上有很多卖票员。LC同学分到了第L号票到第R号票。因为一些神奇的东西，第I号票对应的船舱能坐的人恰好是I的各位数字之和。地球上有很多大家族，每个家族都有M个人，同时每个家族都想买一些连续的票位使他们家族的人都能坐的上船。大家族都很排外，不肯跟别人共享一张票对应的船舱。 LC同学想知道他在把票都卖光的情况下，能服务几个大家族呢？

Input

一行三个数L,R,M

Output

一行一个数表示结果。

Sample Input

40 218 57

Sample Output

HINT

100%的数据 l,r<=10^18 ,M<=1000 50%的数据，r-l<=10^6

Source

和谐社会模拟赛 Sgu390

分析：

这题目名字很NB，思想也很NB...我们一起来膜拜论文~~~

这个论文里面的思想大概都是用多叉树来实现的数位DP...

代码：

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

//by NeighThorn

using namespace std;

long long l,r,m;

int cntl,cntr,nol[18+5],nor[18+5];

struct M{

	long long x,y;

	M(long long a=0,long long b=0){

		x=a,y=b;

	}

	inline void init(void){

		x=-1,y=0;

	}

	friend M operator + (M a,M b){

		M res;

		res.x=a.x+b.x;

		res.y=b.y;

		return res;

	}

}f[19][201][1001];

inline M dfs(int dep,long long sum,long long rem,bool lf,bool rf){

	if(!dep)

		return sum+rem>=m?M(1,0):M(0,sum+rem);

	if(!lf&&!rf&&f[dep][sum][rem].x!=-1)

		return f[dep][sum][rem];

	M ans=M(0,rem);

	for(int i=(lf?nol[dep]:0);i<=(rf?nor[dep]:9);i++)

		ans=ans+dfs(dep-1,sum+i,ans.y,lf&&i==nol[dep],rf&&i==nor[dep]);

	if(!lf&&!rf)

		f[dep][sum][rem]=ans;

	return ans;

}

signed main(void){

#ifndef ONLINE_JUDGE

	freopen("in.txt","r",stdin);

#endif

	scanf("%lld%lld%lld",&l,&r,&m);

	while(l) nol[++cntl]=l%10,l/=10;

	while(r) nor[++cntr]=r%10,r/=10;

	for(int i=0;i<=18;i++)

		for(int j=0;j<=200;j++)

			for(int k=0;k<=1000;k++)

				f[i][j][k].init();

	printf("%lld\n",dfs(cntr,0,0,1,1).x);

	return 0;

}

By NeighThorn

巴特西