首页 > 代码库 > 【bzoj3598】 Scoi2014—方伯伯的商场之旅
【bzoj3598】 Scoi2014—方伯伯的商场之旅
http://www.lydsy.com/JudgeOnline/problem.php?id=3598 (题目链接)
题意
Solution
原来这就是极水的数位dp,呵呵= =,感觉白学了。http://www.cnblogs.com/Artanis/p/3751644.html
首先我们考虑集结点设置第一位(最低位)上,数位dp计算出此时的代价。
如果将集结点往高位移动一位,那么此时代价会怎么变化呢,位置比集结点高的数位上的数它们的距离全部-1,位置比集结点低的数位上的数它们的距离全部+1。所以我们再数位dp,计算出变化值,舍弃变化值<0的数,将答案更新。
细节
LL,枚举是1~K-1
代码
// bzoj3598#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<ctime>#define LL long long#define inf (1ll<<30)#define MOD 1000000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;LL f[60][3000],l,r;int K,n,t[60];LL dfs(int pos,int s,int lim) { if (pos==0) return s; if (!lim && f[pos][s]!=-1) return f[pos][s]; int end=lim ? t[pos] : K-1; LL res=0; for (int i=0;i<=end;i++) res+=dfs(pos-1,s+i*(pos-1),lim && i==end); if (!lim) f[pos][s]=res; return res;}LL dfs(int pos,int s,int m,int lim) { if (s<0) return 0; if (pos==0) return s; if (!lim && f[pos][s]!=-1) return f[pos][s]; int end=lim ? t[pos] : K-1; LL res=0; for (int i=0;i<=end;i++) { if (pos>=m) res+=dfs(pos-1,s+i,m,lim && i==end); else res+=dfs(pos-1,s-i,m,lim && i==end); } if (!lim) f[pos][s]=res; return res;}LL solve(LL x) { for (n=0;x;x/=K) t[++n]=x%K; memset(f,-1,sizeof(f)); LL res=dfs(n,0,1); for (int i=2;i<=n;i++) { memset(f,-1,sizeof(f)); res-=dfs(n,0,i,1); } return res;}int main() { scanf("%lld%lld%d",&l,&r,&K); printf("%lld\n",solve(r)-solve(l-1)); return 0;}
【bzoj3598】 Scoi2014—方伯伯的商场之旅
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。