BZOJ 3131 [Sdoi2013] 淘金

Description

小Z在玩一个叫做《淘金者》的游戏。游戏的世界是一个二维坐标。X轴、Y轴坐标范围均为1..N。初始的时候，所有的整数坐标点上均有一块金子，共N*N块。一阵风吹过，金子的位置发生了一些变化。细心的小Z发现，初始在(i，j)坐标处的金子会变到(f(i)，fIj))坐标处。其中f(x)表示x各位数字的乘积，例如f(99)=81，f(12)=2，f(10)=0。如果金子变化后的坐标不在1..N的范围内，我们认为这块金子已经被移出游戏。同时可以发现，对于变化之后的游戏局面，某些坐标上的金子数量可能不止一块，而另外一些坐标上可能已经没有金子。这次变化之后，游戏将不会再对金子的位置和数量进行改变，玩家可以开始进行采集工作。小Z很懒，打算只进行K次采集。每次采集可以得到某一个坐标上的所有金子，采集之后，该坐标上的金子数变为0。现在小Z希望知道，对于变化之后的游戏局面，在采集次数为K的前提下，最多可以采集到多少块金子？答案可能很大，小Z希望得到对1000000007(10^9+7)取模之后的答案。

Input

共一行，包含两介正整数N，K。

Output

一个整数，表示最多可以采集到的金子数量。

Sample Input

1 2 5

Sample Output

HINT

N < = 10^12 ,K < = 100000 对于100%的测试数据：K < = N^2

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

数位DP+优先队列+STL~

首先，数的状态不多，只有10000+，所以我们可以先dfs一遍求出所有数，排序去重，再借助lower_bound()快捷地寻找该数的位置，这样就方便了DP过程中的记录。

用f[i][j][k]表示目前在第i位，所有位乘积为j，当前数(z==1 ? >:<=)原数N的数的个数。

然后用优先队列找出最大的k个，更新答案~

（另：样例好像有问题，应该是1。）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
#define modd 1000000007

int k,a[15],len,tot,ans;
ll n,dis[400001],f[15][15000][2],siz[15000],totnum,num[15000];

struct node{
	int x,y;
	ll val;
	node(int u,int v)
	{
		x=u;y=v;
		val=(ll)siz[num[u]]*siz[num[v]];
	}
};

PRiority_queue<node> q;

bool Operator < (node u,node v)
{
	return u.val<v.val;
}

bool cmp(int u,int v)
{
	return siz[u]>siz[v];
}

void dfs(int u,int v,ll kk)
{
	if(v>len)
	{
		dis[++tot]=kk;return;
	}
	if(!kk) return;
	for(int i=u;i<10;i++) dfs(i,v+1,kk*i);
}

int main()
{
	scanf("%lld%d",&n,&k);
	while(n)
	{
		a[++len]=n%10;n/=10;
	}
	dfs(0,0,1);dis[++tot]=0;
	sort(dis+1,dis+tot+1);
	tot=unique(dis+1,dis+tot+1)-dis-1;
	f[0][2][0]=1;
	for(int i=0;i<=len;i++)
	  for(int j=1;j<=tot;j++)
	    for(int k=0;k<=1;k++)
	      if(f[i][j][k])
	        for(int z=i ? 1:0;z<10;z++)
	          f[i+1][lower_bound(dis+1,dis+tot+1,dis[j]*z)-dis][k+z>a[i+1]]+=f[i][j][k];
	for(int i=1;i<=tot;i++)
	{
		num[i]=i;
		for(int j=1;j<len;j++) siz[i]+=f[j][i][0]+f[j][i][1];
		siz[i]+=f[len][i][0];
	}
	sort(num+2,num+tot+1,cmp);
	q.push(node(2,2));
	while(!q.empty())
	{
		node tmp=q.top();q.pop();
		ans=(ans+tmp.val)%modd;totnum++;
		if(totnum==k) break;
		if(tmp.x!=tmp.y)
		{
			ans=(ans+tmp.val)%modd;totnum++;
			if(totnum==k) break;
			q.push(node(tmp.x+1,tmp.y));
		}
		if(tmp.x==2) q.push(node(tmp.x,tmp.y+1));
	}
	printf("%d\n",ans);
	return 0;
}