数据淼

回复 @CSY.Girl_Queen :
对于一个问题而言，存在某种贪心策略可得到局部最优解。
但是若证明该贪心策略所得到的局部最优解亦是全局最优解仍需严格的证明过程。
在这里，我误认为三集合就可以表示所有的状态，但是存在以下问题：
1。集合$ABC$都代表着在全局中始终为最优解的集合。却无法确定集合的合并方式。
2.无法确定先选取哪个集合为B进行合并$(A(BCD)),((ABC)D)$

挂了N次。。。

回复 @CH.Genius_King :
我将反例用统一的形式表示，可表示为4种状态的情况。
设状态集合$A,B,C,D$，形式可以包含多种决策，但他们在形式上是统一的。
形式1双双合并再合并
$F(ABCD)=W(A)+W(B)+W(C)+W(D)+W(AB)+W(CD)$
形式2逐次相邻合并型
$F(ABCD)=W(A)+W(B)+W(AB)+W(C)+W(ABC)+W(D)$
形式1$δ(ABCD)=W(D)$
形式2$δ(ABCD)=W(AB)$

然后我就无意间又证明贪心算法是对的！

我们都知道这是一道很基础的DP。
$F$为所需求的状态值，在石子归并问题中理解为权重。$W$为物品重量，$φ$为与参数(状态$K$)相关的状态转移权重。
$F(A)=Min(F(A-K)+φ(K))$类型的动归(A,K表状态集合，在石子归并问题中我们使它内部元素有序)。
在石子归并问题中，我们认为$φ(K)=W(A)+W(A-K)$
可是，如何证明它不可以使用贪心算法呢？
假设有序集合$A,B,C$表示不同的状态。终止状态为$(ABC)$初始价值(状态)则为$Ω(INIT)=F(A)+F(B)+F(C)$
策略1$F(ABC)=W(A)+W(B)+W(AB)+W(ABC)+Ω(INIT)$
策略2$F(ABC)=W(B)+W(C)+W(BC)+W(ABC)+Ω(INIT)$
两式比较取差异部分：
策略1$δ(ABC)=2W(A)$
策略2$δ(ABC)=2W(C)$
此时的可以看出在初末状态相同时，策略1与策略2有明显的优劣。我们只需修改$ABC$集合代表的状态（只需保证其始终为有序态即可），既可以得到全局最优解

这也太快了……

这题目不科学啊……传感器阵列毛线啊……
题中的图是HAARP（我自己加的，原题上没有），估计原题作者看这个看多了……
但是用来监测飞机的雷达真·不这样啊……远程预警雷达是一个一大坨，而不是阵列……

儿童机协会
Association of Children Machines,ACM
笑尿

输出格式错了。
唉..

难道没有人吐槽题中给的例子（不是样例）错了么？

论树状数组的灵活运用

天哪，少个+1 居然过了4个点 错误代码139 136的飞……
PS:我是蓝字菌

数据 暴弱 ，居然可以不回退。。。我有一组 暴强 数据用我的代码过不去#7,#8点

原来路径覆盖是这么拆点的……
WC2014发来贺电

我用long，long但结果是long。
@@ -2793 +2793 @@
--1849811792
+2445155504
@@ -2819 +2819 @@
--2091217477
+2203749819
@@ -3001 +3001 @@
--2040892038
+2254075258
@@ -3012 +3012 @@
--2084295718
+2210671578
@@ -3104 +3104 @@
--1731122940
+2563844356
@@ -3118 +3118 @@
--2140405080
+2154562216
@@ -3280 +3280 @@
--2138769060
+2156198236
@@ -3296 +3296 @@
--1899103816
+2395863480
@@ -3415 +3415...

水题，挺简单的

回复 @常可神牛 : 不愧是神牛！

回复 @哈凌大侠 : 不用，longint足以，我就是这么过的。

加上读入优化还是过不了，但下了数据到本地就能很快出解，评测机太慢？

注意有些点不连通的情况。。。:(