题目大意
给出一个区间，将这个区间连续的数的数位加起来，保证和要不小于$k$，求能分的最多区间。
题目分析
这题比较难。
和以往的数位动规的区别是：要求加上区间连续的每个数的数位和。
按照以往的数位动规方法是无法处理的。
考虑如何表示出所有数的数位：我们可以将所有数位展开成为十叉树，每个数对应了根到叶子结点的一段路径。
我们需要统计的是$x$对应路径右，$y$对应路径左边部分的所有数，对它们进行Dp。
考虑从根往下Dp，设状态$f[i,j,k]$表示一个二元组$(first,second)$。$f[i,j,k].first$表示第$i$个数位，到当前结点的路径左方的子树数位和为$j$（不包括正在遍历的路径），当前路径的数位和为$k$所形成的最多区间数。$f[i,j,k].second$表示$\cdots\cdots$路径下方子树和。枚举每一位的数进行转移即可（屠龙代码一看就懂）。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
#define pii pair<LL,LL>
#define mp make_pair
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
LL x,y,k;
int high[25],low[25];
bool vst[25][1005][165];
pii f[25][1005][165];
pii Dp(int Now,int last,int sum,bool down,bool up) {
if(Now<0) {
if(last+sum>=k)return mp(1,0);
else return mp(0,last+sum);
}
if(!down&&!up&&vst[Now][last][sum])return f[Now][last][sum];
int lowbit=down?low[Now]:0,highbit=up?high[Now]:9;
pii ans=mp(0,last);
for(int i=lowbit; i<=highbit; i++) {
pii tmp=Dp(Now-1,ans.second,sum+i,down&&i==lowbit,up&&i==highbit);
ans.first+=tmp.first;
ans.second=tmp.second;
}
if(!down&&!up) {
vst[Now][last][sum]=1;
f[Now][last][sum]=ans;
}
return ans;
}
int main() {
x=Get_Int();
y=Get_Int();
k=Get_Int();
int cntlow=0,cnthigh=0;
while(x) {
low[cntlow++]=x%10;
x/=10;
}
while(y) {
high[cnthigh++]=y%10;
y/=10;
}
printf("%lld\n",Dp(cnthigh-1,0,0,1,1).first);
return 0;
}
|
