2063: 我爸是李刚

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 139  Solved: 72
[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

29

HINT

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

Source

和谐社会模拟赛 Sgu390

Solution

详见 2009年国家集训队论文 ,这类题之前真的没见过,没啥好说的。

【BZOJ-2063】我爸是李刚      数位dp 好题-LMLPHP【BZOJ-2063】我爸是李刚      数位dp 好题-LMLPHP

Code

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
#define LL long long
#define Pa pair<LL,LL>
#define sum first
#define res second
#define MP make_pair LL L,R,M;
int dl[19],dr[19],len; Pa dp[19][210][1010]; Pa operator + (const Pa &A,const Pa &B) {return MP(A.sum+B.sum,B.res);} inline Pa DP(int dep,LL sum,LL res,bool f,bool g)
{
if (!dep) return (sum+res>=M? MP(1LL,0LL):MP(0LL,sum+res));
if (!f && !g && ~dp[dep][sum][res].sum) return dp[dep][sum][res];
Pa ret=MP(0,res);
for (int i=(f? dl[dep]:0); i<=(g? dr[dep]:9); i++)
ret=ret+DP(dep-1,sum+i,ret.res,f && i==dl[dep],g && i==dr[dep]);
if (!f && !g) dp[dep][sum][res]=ret;
return ret;
} int main()
{
scanf("%lld%lld%lld",&L,&R,&M);
len=0; while (L) dl[++len]=L%10,L/=10;
len=0; while (R) dr[++len]=R%10,R/=10;
for (int i=1; i<=18; i++)
for (int j=0; j<=200; j++)
for (int k=0; k<=1000; k++)
dp[i][j][k]=MP(-1,0);
printf("%lld\n",DP(len,0,0,1,1).sum);
return 0;
}

  

05-11 18:04