SGU 390 Tickets （数位dp好题）

题意：

你有编号为L到R的钞票，钞票的价值就是它的编号的各个位数字之和（比如编号218的价值就是11）。现在有很多人排着队，你要从编号为L的钞票开始一直给同一个人，给完编号x的钞票再给编号x+1的钞票，直到他手上的价值>=k，换下一个人继续给。问最多能给多少个人使他们手上的价值都>=k。

做法：

先考虑按位暴搜，dfs到n+1的时候其实相当于枚举了一个x（L<=x<=R）。这时候需要知道这个x前面已经累加了多少价值，然后把这个x和之前累加起来的价值合并一下。最后退出递归的时候其实就已经把所有的x从L到R都枚举了一遍，并且返回了合并的结果。

最后记忆化一下复杂度就完美了。

讲不清啊，还是看代码吧

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
char sl[30],sr[30];
int n,k;
struct P
{
	ll num,left;
	P()
	{
		num=left=-1;
	}
	P(ll x,ll y)
	{
		num=x; left=y;
	}
	void operator +=(const P &t)
	{
		num+=t.num;
		left+=t.left;
		num+=left/k;
		left%=k;
	}
}f[20][2][2][170][1005];
P dfs(int pos,bool dn,bool up,int dg,int lft) //dg表示枚举到这一位的数字和，lft表示当前还不足k的积累的价值
{
	if (pos>n)
	{
		if ((lft+dg>=k)) return P(1,0);  // 加上它满k了，多余的就没用了
		return P(0,lft+dg);   //加上它不满k，继续积累
	}
	P ret=f[pos][dn][up][dg][lft];
	if (ret.num!=-1) return ret;
	ret=P(0,lft);
	for (int i=0;i<=9;i++)
	{
		if (dn&&i<sl[pos]-'0') continue;
		if (up&&i>sr[pos]-'0') continue;
		bool ddn=dn; if (i>sl[pos]-'0') ddn=0;
		bool uup=up; if (i<sr[pos]-'0') uup=0;
		int ddg=dg+i;
		P tmp=dfs(pos+1,ddn,uup,ddg,ret.left);  //把ret的剩余部分传递到后面那些数
		ret.left=0;  //ret的剩余部分已经传递了，就要清零
		ret+=tmp;
	}
	return f[pos][dn][up][dg][lft]=ret;
}
int main()
{
	scanf("%s%s%lld",sl+1,sr+1,&k);
	n=strlen(sr+1);
	int m=strlen(sl+1);
	for (int i=m;i>=1;i--) sl[i+(n-m)]=sl[i];
	for (int i=1;i<=n-m;i++) sl[i]='0';   //把数字弄成相同长度，前面补零
	printf("%lld\n",dfs(1,1,1,0,0).num);
}
//http://paste.ubuntu.com/18608740/    原始版本