题解 P3286 【[SCOI2014]方伯伯的商场之旅】

shadowice1984

2018-09-01 13:12:38

Solution

## 本题题解 先来考虑一个特殊的情况,如果只有一个数字,那么我们该如何挪动石子才能使得总代价最小 换句话说我们的目标是最小化每个石子到集合点的距离之和 小学数奥告诉我们集合到石子们位置的中位数的位置是最优的 但是,似乎并没什么卵用……,因为我们现在要同时处理很多数字 那么我们考虑另一种寻求最优解的方法, 其实寻找最优解的过程是可以贪心的 我们先假设一号点就是集合点,求出一个代价 接下来我们尝试将集合点从1号点挪动到2号点,那么代价的变动量就是(1号点的石子数目-编号大于等于2的点的石子数目)如果代价的变动量是负的,我们就将集合点挪到2号点 现在我们的集合点是2号点,我们接着考虑将集合点放到3号点会不会更加优秀,依然求出代价的变化量,这时代价的变化量是(编号小于等于2的点的石子数目-编号大于等于3的点的石子数目),如果代价的变化量是负的我们就将集合点挪到3号点 重复这个贪心流程,直到代价的变化量是正的,我们就停止 为什么这个贪心是对的呢? 因为石子数目肯定是非负的,所以整个数组的前缀和单调不减,整个数组的后缀和单调不增,我们发现刚才贪心过程中代价的变化量其实就是前缀和-后缀和的形式,那么显然这个值一旦变成正的就再也不可能变回负数了,所以我们可以证明这个贪心就是对的 好了那么这个贪心算法有什么用呢? 答案是我们可以对于[l,r]区间里所有的数字同时跑这个贪心算法 一开始先求出所有数字都集合到1号点时的代价之和 _这个东西可以使用数位dp来求解,枚举每一位放什么数字,然后计算代价_ 接下来我们尝试着将集合点挪动到2号点,那么此时有一些数字不会挪动的,有一些数字是会挪动的,我们此时的目标是求出所有挪动了的数字的代价的变化量之和 显然对于一个数字来讲他的答案的变化量就是(前缀和-后缀和),问题来了现在有一堆数字,他们的变化量各不相同,怎么办呢? 观察到前缀和的范围很小,只有250左右,所以我们暴力枚举这些数字的前缀和和后缀和,对每一个变化量求出变化量就是这个值的数字有多少个,然后答案加上变化量×数字个数就行了 那么我们现在要回答的问题就是,第p位之前数位和为pre且第p位之后数位和为suf且这个数字小于x的数字有多少个 这似乎是个经典的数位dp问题 设$dp_{i,j,k,t} t \in \{ 0,1\}$表示决策到了第i位,第p位前的数位和为j,数字的数位和为k,t为0表示这个数字前i位比x的前i小,t为1表示这个数字的前i位和x的前i位一样 那么转移的话十分的simple,只需要枚举下一位填什么数字就行了 求出这个dp数组之后我们就可以回答之前的问题了 然后我们就可以求出将集合点挪动到2之后答案的变化量了 接着重复这个过程,尝试将集合点挪动至第三个点 继续刚才的数位dp,把他再做一遍,只不过这回你的问题中的p由2变成了3,然后求出挪动到3的变化量之和即可 最后当你将集合点挪动到n的时候你就做完了这道题了 当然你可能会觉得刚才的数位dp可能有点不对劲,我是不是还要加上一个这个点之前一直在挪动的限制条件? 事实上这个限制条件是没有必要的,因为我们最后统计的是所有前缀和小于后缀和的数字,既然这个位置它的变化量还是负的,就证明它之前一直在挪动,无需加上这个限制条件 ____________________________________ 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=60;const int M=250;typedef long long ll; ll dp[N][M][M][2];int a[N];ll l;ll r;int n;int jz;ll f[N][2];ll sum[N][2]; inline ll solve(ll x) { ll ret=0;n=0;while(x)a[++n]=x%jz,x/=jz;reverse(a+1,a+n+1);f[0][1]=1; for(int i=0;i<n;i++) { f[i+1][1]+=f[i][1];sum[i+1][1]+=sum[i][1]+f[i][1]*a[i+1]*i; for(int t=0;t<a[i+1];t++)f[i+1][0]+=f[i][1],sum[i+1][0]+=sum[i][1]+f[i][1]*t*i; for(int t=0;t<jz;t++)f[i+1][0]+=f[i][0],sum[i+1][0]+=sum[i][0]+f[i][0]*t*i; }ret=sum[n][0]+sum[n][1]; for(int i=0;i<=n;i++)sum[i][0]=sum[i][1]=0;for(int i=1;i<=n;i++)f[i][0]=f[i][1]=0; for(int nl=1;nl<n;nl++) { dp[0][0][0][1]=1; for(int i=0;i<n;i++) if(i+1<=nl) { for(int j=0;j<=i*jz;j++) { if(dp[i][j][j]==0)continue; dp[i+1][j+a[i+1]][j+a[i+1]][1]+=dp[i][j][j][1]; for(int t=0;t<a[i+1];t++)dp[i+1][j+t][j+t][0]+=dp[i][j][j][1]; for(int t=0;t<jz;t++)dp[i+1][j+t][j+t][0]+=dp[i][j][j][0]; } } else { for(int j=0;j<=i*jz;j++) for(int k=0;k<=nl*jz;k++) { if(dp[i][j][k]==0)continue; dp[i+1][j+a[i+1]][k][1]+=dp[i][j][k][1]; for(int t=0;t<a[i+1];t++)dp[i+1][j+t][k][0]+=dp[i][j][k][1]; for(int t=0;t<jz;t++)dp[i+1][j+t][k][0]+=dp[i][j][k][0]; } } for(int pre=0;pre<=nl*jz;pre++) for(int suf=pre+1;suf+pre<=n*jz;suf++) ret-=(suf-pre)*(dp[n][suf+pre][pre][0]+dp[n][suf+pre][pre][1]); for(int i=0;i<=n;i++) for(int j=0;j<=i*jz;j++) for(int k=0;k<=nl*jz;k++)dp[i][j][k][0]=dp[i][j][k][1]=0; }return ret; } int main(){scanf("%lld%lld%d",&l,&r,&jz);printf("%lld",solve(r)-solve(l-1));return 0;} ```