BZOJ.3598.[SCOI2014]方伯伯的商场之旅(贪心 数位DP)
题目链接 先考虑，对于确定的一个数，怎样移动代价最少（或者移到哪个位置最优）？ 假设我们都移到下标\(1\)位置（设集合点为\(1\)），那么移动到下标\(2\)与\(1\)相比代价差为：\(下标<1的石子数和-下标>1的石子数和\)。 如果它为负，那么把移到\(1\)的代价加上它，令集...
[SCOI2014]方伯伯的商场之旅
题面 数位dp #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...
bzoj3598[SCOI2014]方伯伯的商场之旅
数位DP三大核心思想：1.区间求和转化为前缀和相减 2.逐位确定 3.不对拍基本要完 对于这道题,我们首先考虑单个数字的最优解是什么.找一下规律发现应当把所有数字集中在原先数字总和一半的地方. 不妨想象一个直线上有n个点,找一个点到n个点距离之和最小,那么就是最中间的两个点。这道题相当于一个位置可以...
数位dp [SCOI2014]方伯伯的商场之旅
https://www.luogu.org/problemnew/show/P3286 我当时在考场上的时候考虑两边的数位dp 但是要处理是否有\(limit\) 非常的麻烦 然后就续了好久没有续出来 后来看到一个很棒的做法 就是刚开始的时候钦点一个汇集点\(1\)算出答案 然后考虑移动汇集点减少的...
Bzoj3597: [Scoi2014]方伯伯运椰子
题面 传送门 Sol 消圈定理：如果一个费用流网络的残量网络有负环，那么这个费用流不优 于是这个题就可以建出残量网络，然后分数规划跑负环了 # include <bits/stdc++.h># define IL inline# define RG register# define ...
【数位dp】[Scoi2014] bzoj3598 方伯伯的商场之旅
题目点这里 和方伯伯的斗争终于结束了。。。我也是快要死了。。。。（请自动忽视那两道非人哉的题 = =） 之前听学长说这题很水的数位dp ：） 对 水到我都做不起了。 = =题解看了三遍啊！！！还是没研究明白这踏马是什么鬼！！ ……总有种我数位dp白学了的感觉（其实确实也是白学了） 思路…...
【SCOI2014】【BZOJ3598】方伯伯的商场之旅（数位dp）
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3598 题意： 对于一个数x，它含有一些小石子，每个石子的值为a[i]（a[i]为x在k进制下的第i位），选一个石子的位置pos使得sum(a[i] * abs(i-pos))最小。 求出[L,...
BZOJ3598 SCOI2014方伯伯的商场之旅（数位dp）
看到数据范围就可以猜到数位dp了。显然对于一个数最后移到的位置应该是其中位数。于是考虑枚举移到的位置，那么设其左边和为l，左右边和为r，该位置数为p，则需要满足l+p>=r且r+p>=l。同时为了防止重复，枚举的应该是最左的能移到的位置，那么还需要满足l<p+r。算的时候枚举p、l...
洛谷 P3286 [SCOI2014]方伯伯的商场之旅
题面 题意 给出l,r,k,求将l与r之间的数进行x操作的最小代价. x操作指将一个数转化为k进制,表示有几堆石块,每对石块恰有该数位上的数个石子,相邻两堆距离为1,将它们并成一堆,代价为石头数量*距离. 做法 因为l和r的范围都高达1e15,故考虑数位dp,而此题难点...
bzoj 3598: [Scoi2014]方伯伯的商场之旅【数位dp】
参考了这个http://www.cnblogs.com/Artanis/p/3751644.html，好像比一般方法好写 大概思想就是先计算出把所有石子都合并到1位置的代价，这样显然有一些是不优的，然后再分别计算把合并到1的石子合并到p，能优化多少 这个计算就是枚举2到tot位，对于每一位计算挪到这...
bzoj 3598 [Scoi2014]方伯伯的商场之旅 数位dp
当位置向后移动时，可以发现答案加上前面一段所有数字之和减去后面一段所有数字之和。 然后前面一段所有数字之和单调不减，后面一段所有数字之和单调不增。 为了避免重复找最前面的满足的点。设答案的位置为a1，a1的下一个位置为a2。 应该选取的位置满足 s1<a1+a2+s2 ...
bzoj3598: [Scoi2014]方伯伯的商场之旅
传送门 大佬的题解：哇我省选秒A了这道题，不过就是一道水题嘛 我：？？？ 奥妙重重的数位dp，虽然其实似乎比数数好一点。 先考虑把所有石头都移到第1堆，记忆化搜索算出总贡献。 然后把石头往后移，记忆化搜索n次，第i次搜索算出把那些从i移动到i+1可以减少代价的石头堆移到i+1减少的代价。 ...
【BZOJ3598】【SCOI2014】方伯伯的商场之旅
Description 方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。说来也巧，位置在 i 的人面前的第 j 堆的石子的数量，刚好是 i 写成 K 进制后的第 j 位。 现在方伯伯要玩一个游戏，商场会给方伯伯两个整数 L,R。方伯伯要把位置在 [L,...
bzoj3598 [Scoi2014]方伯伯的商场之旅
数位dp，我们肯定枚举集合的位置，但是如果每次都重新dp的话会很麻烦，所以我们可以先钦定在最低位集合，dp出代价，然后再一步步找到正确的集合点，每次更改的代价也dp算就好了。 1 #include <cstdio> 2 #include <cstring> 3 #...
bzoj 3594 [Scoi2014]方伯伯的玉米田
http://www.elijahqi.win/archives/3683 Description 方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。 这排玉米一共有N株，它们的高度参差不齐。 方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉...
bzoj 3594: [Scoi2014]方伯伯的玉米田 dp树状数组优化
3594: [Scoi2014]方伯伯的玉米田Time Limit: 60 Sec Memory Limit: 128 MBSubmit: 314 Solved: 132[Submit][Status]Description方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。这排玉米一...
分数规划 spfa [SCOI2014]方伯伯运椰子
https://www.luogu.org/problemnew/show/P3288 今天比赛被第二题续了 gg..看到有一个分数 然后分数规划一下然后就不知道怎么做了正解好像挺简单的根据流量守恒 所以消出来的是一个圈建一个新图 边权为退流以及加流的费用费用变小就判一个负圈就好了注意加边的时候要判...
「SCOI2014」方伯伯运椰子 解题报告
「SCOI2014」方伯伯运椰子 可以看出是分数规划 然后我们可以看出其实只需要改变1的流量就可以了，因为每次改变要保证流量守恒，必须流成一个环，在正负性确定的情况下，变几次是无所谓的。 然后按照套路，设\[ ans=\frac{X-Y}{k}\\ ans\times k =X-Y\\ ans\ti...
bzoj 3597: [Scoi2014]方伯伯运椰子 0/1分数规划
3597: [Scoi2014]方伯伯运椰子Time Limit: 30 Sec Memory Limit: 64 MBSubmit: 144 Solved: 78[Submit][Status][Discuss]Description.................Input第一行包含二个整...
[SCOI2014]方伯伯的商场之旅
题面 数位dp #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...