[bzoj3598]-[SCOI2014]方伯伯的商场之旅

发布于 2018-03-14  22 次阅读



题目(BZOJ)
题目(洛谷)
 
这个数位dp感觉算水的吧......
首先,我们设每一个人的集结点为1,统计一次答案,然后依次集结点依次往右,看每个点减少了多少(减少值<0说明代价增加,直接return 0),就可以了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
ll L,R,K;
ll dp[70][3050];bool vis[70][3050];
int n,b[70];
ll dfs1(int pos,int cost,bool lim){
	if(!pos)return cost;
	if(!lim&&vis[pos][cost])return dp[pos][cost];
	int up=lim?b[pos]:K-1;
	ll ret=0;
	for(int i=0;i<=up;++i)
		ret+=dfs1(pos-1,cost+i*(pos-1),lim&&i==up);
	if(!lim)vis[pos][cost]=1,dp[pos][cost]=ret;
	return ret;
}
ll dfs2(int pos,int cost,int mid,bool lim){
	if(cost<0)return 0;
	if(!pos)return cost;
	if(!lim&&vis[pos][cost])return dp[pos][cost];
	int up=lim?b[pos]:K-1;
	ll ret=0;
	for(int i=0;i<=up;++i){
		if(pos>=mid)ret+=dfs2(pos-1,cost+i,mid,lim&&i==up);
		else ret+=dfs2(pos-1,cost-i,mid,lim&&i==up);
	}
	if(!lim)vis[pos][cost]=1,dp[pos][cost]=ret;
	return ret;
}
inline ll solve(ll x){
	n=0;while(x)b[++n]=
	memset(vis,0,sizeof vis);
	memset(dp,0,sizeof dp);
	ll ret=dfs1(n,0,1);
	for(int i=2;i<=n;++i){
		memset(vis,0,sizeof vis);
		memset(dp,0,sizeof dp);
		ret-=dfs2(n,0,i,1);
	}
	return ret;
}
int main(){
	read(L),read(R),read(K);
	printf(
	return 0;
}