SGU_390_Tickets(另类数位DP)
Tickets
Time Limit : 1000/500ms (Java/Other) Memory Limit : 524288/262144K (Java/Other)
Total Submission(s) : 79 Accepted Submission(s) : 16
Conductor is quite a boring profession, as all you have to do is just to sell tickets to the passengers. So no wonder that once upon a time in a faraway galaxy one conductor decided to diversify this occupation. Now this conductor sells several tickets at a
time to each passenger. More precisely, he successively gives tickets to the passenger until the sum of the digits on all the tickets given becomes not less than some integer number k. Then this process repeats for the next passenger. Initially conductor
has a tape of tickets numbered successively from l to r, inclusive. This way of tickets distribution is quite good, because passengers are glad to get several tickets when they pay only for one. But there is one disadvantage. Since each passenger
gets several tickets, it is possible that conductor won't be able to serve all passengers. Your task is to help conductor in this difficult situation. You should calculate how many passengers is the conductor able to serve.
Input file contains three integer numbers l, r and k (1 ≤ l ≤ r ≤ 1018, 1 ≤ k ≤ 1000).
Output should contain exactly one number — the answer to the problem.
sample input |
sample output |
40 218 57 |
29 |
题意:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long LL;
typedef pair<LL,LL>P;
int l[],r[],ln,rn,vis[][][];
LL a,b,m;
P dp[][][];
P dfs(int pos=rn,int sum=,int rem=,bool up=,bool dn=){
if(!pos)if(sum+rem>=m)return P(,);else return P(,sum+rem);
if(vis[pos][sum][rem]&&!up&&!dn)return dp[pos][sum][rem];
int st=dn?l[pos]:,end=up?r[pos]:;P ans=P(,rem);
F(i,st,end){
P tp=dfs(pos-,sum+i,ans.second,up&&i==end,dn&&i==st);
ans.first+=tp.first,ans.second=tp.second;
}
if(!up&&!dn)dp[pos][sum][rem]=ans,vis[pos][sum][rem]=;
return ans;
} int main(){
while(~scanf("%I64d%I64d%I64d",&a,&b,&m)){
memset(vis,,sizeof(vis));
for(rn=;b;b/=)r[++rn]=b%;
for(ln=;ln<rn;a/=)l[++ln]=a%;
printf("%I64d\n",dfs().first);
}
return ;
}
最新文章
- SharePoint如何将使列表不被爬网爬到。
- weex scroller
- Java的发展历程
- Ajax参数详解
- 【CodeVS 1199】【NOIP 2012】开车旅行
- 开源License
- Java中Set集合的使用
- 【P1304】【P1305】选课与选课输出方案
- EasyUI 使用注意点
- java的";==";与";equals";
- SQLite数据库安装与使用
- LeetCode 169. Majority Element (众数)
- angular2 表单验证
- __call PHP伪重载方法
- mysql批量插入语句执行失败的话,是部分失败还是全部失败
- Vue入门:Vue环境安装
- 微软Azure AspNetCore微服务实战第1期【补充2017-09-09活动】
- [db]mysql全量迁移db
- SpringMVC之声明式校验
- luogu2542 航线规划 (树链剖分)