題意：給定 $l,r,k$ ，對于一個 $k$ 進制數，將數碼看成這個位置的石子個數，每將一個石子移動 $1$ 的距離需要 $1$ 的代價。求 $[l,r]$ 中的所有數在 $k$ 進制下將石子集中在一個位置的最小代價之和。

$l\le r\le 10^{15},k\le 20$

對于序列 $\{a_1,a_2,\dots ,a_n\}$，顯然將集中位置從 $k?1$ 移動到 $k$ 會減少 ${\sum }_{i=k}^n{a}_i?{\sum }_{i=1}^{k?1}{a}_i$ 的代價。

枚舉最優的位置，卡下前后的和的上下界，就可以數位 dp 了。

然而這個東西十分精神污染，反正我寫了一天沒寫出來。

考慮更優美的做法。發現這個代價是關于集中位置的單峰函數，也就是一次往后移動如果貢獻為負，那之后的貢獻都為負。

所以有這樣一個思路：先統計出放在最高位的總貢獻，然后考慮每個移動產生的貢獻，如果為正就把它加上。

可以設 $dp(p,i,s,lim)$ 表示從高到低考慮到第 $i$ 位，如果把未考慮的記為 $0$，高于 $p$ （含）的數碼和減去低于 $p$ （不含）的數碼和為 $s$，是否卡上界的總貢獻。 $p=1$ 的時候因為要算總貢獻，要特殊處理一下。

為什么數位 dp 記憶化搜索這么好寫啊……

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> using namespace std; typedef long long ll; int B; int a[55],cnt,p; ll f[55][20005]; ll dfs(int i,int s,int lim) {if (!i||s<0) return max(s,0);if (!lim&&~f[i][s]) return f[i][s];int mx=lim? a[i]:B-1;ll ans=0;for (int x=0;x<=mx;x++)ans+=dfs(i-1,s+(p==1? x*(i-1):(i<p? -x:x)),lim&&x==mx);if (!lim) f[i][s]=ans;return ans; } inline ll calc(ll n) {cnt=0;while (n) a[++cnt]=n%B,n/=B;memset(f,-1,sizeof(f)),p=1;ll ans=dfs(cnt,0,1);for (p=2;p<=cnt;p++) memset(f,-1,sizeof(f)),ans-=dfs(cnt,0,1);return ans; } int main() {ll l,r;cin>>l>>r>>B;cout<<calc(r)-calc(l-1);return 0; }

總結

以上是生活随笔為你收集整理的【SCOI2014】方伯伯的商场之旅【数位dp】【单峰函数】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。