bzoj 3598 方伯伯的商场之旅

Written with StackEdit.

Description

方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。说来也巧，位置在 (i) 的人面前的第(j) 堆的石子的数量，刚好是 (i) 写成 (K) 进制后的第 (j) 位。

现在方伯伯要玩一个游戏，商场会给方伯伯两个整数(L,R)。方伯伯要把位置在 ([L, R])中的每个人的石子都合并成一堆石子。每次操作，他可以选择一个人面前的两堆石子，将其中的一堆中的某些石子移动到另一堆，代价是移动的石子数量 * 移动的距离。商场承诺，方伯伯只要完成任务，就给他一些椰子，代价越小，给他的椰子越多。所以方伯伯很着急，想请你告诉他最少的代价是多少。

例如：10 进制下的位置在 12312 的人，合并石子的最少代价为：

(1 * 2 + 2 * 1 + 3 * 0 + 1 * 1 + 2 * 2 = 9)

即把所有的石子都合并在第三堆.

Input

输入仅有 1 行，包含 3 个用空格分隔的整数 (L，R，K)，表示商场给方伯伯的 2 个整数，以及进制数.

Output

输出仅有 1 行，包含 1 个整数，表示最少的代价.

Sample Input

3 8 3

Sample Output

Hint

(1 < = L < = R < = 10^{15}, 2 < = K < = 20)

Solution

考虑数位dp计算出([1,R])的答案,再减去([1,L-1])的答案.
一开始可以无脑将集结点设置在第1位,用一次数位dp计算出.(dfs1)
然后考虑调整集结点.将集结点从(i)调整至(i+1)对答案造成的影响再用(O(k))次数位dp计算出.(dfs2)
在dfs2中注意若贡献小于0,应返回0,即不执行集结点的调整.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
ll k;
const int MAXN=100;
int t[MAXN],n;
ll f[MAXN][3010];
ll dfs1(int pos,int st,int lim)//数位dp,填到了第pos位,当前总和为st. 
{
	if(pos==0)
		return st;
	if(lim==0 && f[pos][st]!=-1)
		return f[pos][st];
	int mx=lim?t[pos]:k-1;
	ll ans=0;
	for(int i=0;i<=mx;++i)
		ans+=dfs1(pos-1,st+i*(pos-1),lim && i==mx);
	if(lim==0)
		f[pos][st]=ans;
	return ans;
}
ll dfs2(int pos,int st,int m,int lim)//将集结点调节为m的情况下计算最优答案 
{
	if(st<0)
		return 0;
	if(pos==0)
		return st;
	if(lim==0 && f[pos][st]!=-1)
		return f[pos][st];
	int mx=lim?t[pos]:k-1;
	ll ans=0;
	for(int i=0;i<=mx;++i)
		{
			if(pos>=m)
				ans+=dfs2(pos-1,st+i,m,lim && i==mx);
			else
				ans+=dfs2(pos-1,st-i,m,lim && i==mx);
		}
	if(lim==0)
		f[pos][st]=ans;
	return ans;
} 
ll solve(ll x)
{
	for(n=0;x;x/=k)
		t[++n]=x%k;
	memset(f,-1,sizeof f);
	ll res=dfs1(n,0,1);
	for(int i=2;i<=n;++i)//将集结点从i-1调整至i,更新答案. 
		{
			memset(f,-1,sizeof f);
			res-=dfs2(n,0,i,1);
		}
	return res;
}
int main()
{
	ll l=read(),r=read();
	k=read();
	ll ans=solve(r)-solve(l-1);
	printf("%lld
",ans);
	return 0;
}

代码参考了dalao的blog.