[BZOJ 2259]新型计算机

计算机"/>

[BZOJ 2259]新型计算机

写在前面的ps:

你以为set常数大？可是这个程序加了 f r e a d fread fread 跑得飞快（其实不加也挺快）。

前言：

本文使用了动态规划+数据结构来解决此题，如果对数据结构不感兴趣请转其它图论题解代码比我短多了。

另外此题我用了4天超过十个小时来做和调试这道题，求安慰（AC：这个我会

正文：

看到这题正常人第一反应就是暴力规划： f i f_i fi​ 表示将序列前 i i i 个数字设为合法序列的最小代价。不难证明最优子结构性质，无后效性显然。

方程： f [ i ] = m i n f[i] = min f[i]=min{ f [ j ] + ∣ a [ j + 1 ] + j + 1 − i ∣ f[j] + \vert a[j + 1]+j+1-i\vert f[j]+∣a[j+1]+j+1−i∣} ( 0 ≤ j < i ) (0\le j < i) (0≤j<i)

其中边界条件： f [ 0 ] = 0 f[0]=0 f[0]=0。

然后一看 n ≤ 1000000 n\le 1000000 n≤1000000，瞬间心态炸裂……开始在脑中搜索一些奇奇怪怪的数据结构来优化。

显然我们要优化转移过程：不能枚举 f [ j ] f[j] f[j]，而是直接找到最优的 f [ j ] f[j] f[j]。

如果这道题的做法是 O ( n ) O(n) O(n) 的？那……满足条件的数据结构貌似我知道的只有单调队列？

单调队列显然不行啊……方程里有个讨人厌的绝对值，单调性全无……

不过，我们好像可以借鉴一下单调队列的思想？

我们将所有算过的 f i f_i fi​ 放进一个数据结构里。如果存在一个元素 f j f_j fj​，后面任何一个未计算的 f [ i ] f[i] f[i] 的最优解都不可能是这个 f j f_j fj​，则这个元素（ f j f_j fj​）是无用的，应当删除。

显然，方程中的 f [ j ] f[j] f[j] 是固定的，但是 ∣ a [ j + 1 ] + j + 1 − i ∣ \vert a[j + 1]+j+1-i\vert ∣a[j+1]+j+1−i∣ 这一部分会随着 i i i 的增大而变化。

若对于当前的 i i i， a [ j + 1 ] + j + 1 ≤ i a[j + 1]+j+1\leq i a[j+1]+j+1≤i，那么对于后面的所有 i i i，这个绝对值就要开始增大了。否则则一步步减小，直到减少到 0 0 0 后开始增加。

那么我们用一个结构体 n o d e node node 来描述一 f [ j ] f[j] f[j]： n o d e . a = a [ i + 1 ] , n o d e . v = f [ j ] , n o d e . i n d e x = j node.a=a[i+1],node.v=f[j],node.index=j node.a=a[i+1],node.v=f[j],node.index=j。

有了这些信息，方程就可以推着走了。

什么时候 f j f_j fj​ 无论什么时候 一定不如 f i ? f_i? fi​? 当且仅当对于当前正在计算的 f [ k ] ， f [ i ] + ∣ a [ i + 1 ] + i + 1 − k ∣ ≤ f [ j ] + ∣ a [ j + 1 ] + j + 1 − k ∣ f[k]，f[i]+\vert a[i+1]+i+1-k\vert \le f[j]+\vert a[j+1]+j+1-k\vert f[k]，f[i]+∣a[i+1]+i+1−k∣≤f[j]+∣a[j+1]+j+1−k∣，且 a [ i + 1 ] + i + 1 ≥ a [ j + 1 ] + j + 1 a[i+1]+i+1 \ge a[j+1]+j+1 a[i+1]+i+1≥a[j+1]+j+1，则元素 j j j 是无用的，应当及时从表里面删除。

刚才这段话就是我们的核心思想。

然后每计算出一个 f [ i ] f[i] f[i]，包括 f [ 0 ] f[0] f[0]，我们都将其放入表中维护。

如何维护？我们一个元素 i i i 将其按照 a [ i + 1 ] + i + 1 a[i+1]+i+1 a[i+1]+i+1 递减排序即可。当删除所有无用元素后，他们对于当前的 f [ k ] f[k] f[k] 所耗费的代价也是从左往右递减的。

所以，我们需要这个数据结构做的事情是按照 a [ i + 1 ] + i + 1 a[i+1]+i+1 a[i+1]+i+1 排序。 S T L STL STL 中的 s e t set set 就满足这个要求！

然后我就WA25了，经过反复更新和推翻思路……终于找到了问题。。。

尾部的元素很可能也会随着时间推移变得不是最优解！也就是说一个元素 i i i，如果当前正在计算的 f [ k ] f[k] f[k]， a [ i + 1 ] + i + 1 ≤ k a[i+1]+i+1\leq k a[i+1]+i+1≤k，则对于后面的所有 f [ k ] f[k] f[k]， ∣ a [ i + 1 ] + i + 1 − k ∣ \vert a[i+1]+i+1 - k\vert ∣a[i+1]+i+1−k∣ 的值就开始增大了！而很可能其它元素依然在减小，也就是说这个前景不好的元素可能会被淘汰！

所以使用一个指针 p p p 来维护 s e t set set 中 n o d e . a + n o d e . i n d e x + 1 > k node.a+node.index+1>k node.a+node.index+1>k 的最靠前的元素。（也就是说当前正在计算 f [ k ] f[k] f[k]）。

那么代码中 P P P 就是 p p p 的前一个元素，如果 p = N U L L p=NULL p=NULL 或 p = s . b e g i n ( ) p=s.begin() p=s.begin() 则 P = N U L L P = NULL P=NULL。

然后直到 p p p 指向的元素开始不优于它的前一个元素，删除 p p p 指向的元素， p + + p++ p++，即 s . e r a s e ( p + + ) s.erase(p++) s.erase(p++)，如果此时 p = = s . e n d ( ) p==s.end() p==s.end() 则 p = N I E p=NIE p=NIE( N U L L NULL NULL 不能直接赋值给 I t e r a t o r Iterator Iterator， N I E NIE NIE 是程序中一个初始值为 N U L L NULL NULL 的 s t d : : s e t < n o d e > : : i t e r a t o r std::set<node>::iterator std::set<node>::iterator 类型。）

时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。

大体思路就是这样，我也不知道我讲清楚没有……

那么如果本人讲的很烂的话就看这个东西里面的注释吧：

C o d e : Code: Code:

#include <cstdio>
#include <set>
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 65536, stdin), p1 == p2) ? EOF : *p1 ++)
#define abs(k) ((k) < 0 ? ~(k) + 1 : (k))inline int min(int x, int y) {return x < y ? x : y;}char buf[65536], * p1 = buf, * p2 = buf;inline int read() {char ch;int x(0);while ((ch = gc) < 48);while (ch >= 48) x = x * 10 + ch - 48, ch = gc;return x;
}struct node {int a, v, index;node(int _a = 0, int _v = 0, int _Index = 0) {a = _a, v = _v, index = _Index;}inline bool operator < (const node X) const {return a + index + 1 != X.a + X.index + 1 ? a + index + 1 > X.a + X.index + 1 : v < X.v;//即使a+index+1相同也不能乱排，值小的排前面，这样如果插入的是值大的元素会被它的前一个元素删除//否则则会往后删除那个值大的元素}
};int f[1000005], a[1000005];
std::set<node> s;//s中的元素按a+index+1值排序，当删除无用元素后值严格递减 
//如果一个元素a+index+1值比元素x小或相等且值比元素x大或相等则此元素无用 typedef std::set<node>::iterator set_type;set_type NIE(NULL), p(NULL);
inline int Get(set_type sit, int i) {return (* sit).v + abs((* sit).a - i + (* sit).index);}
//计算当前元素sit对于f[i+1]来说所耗的代价
inline int Get2(set_type sit, int j) {return (* sit).v + abs((* sit).a + (* sit).index + 1 - j);}
//计算当前元素sit对于f[j]来说所耗的代价
inline set_type pre(set_type sit) {return sit == NIE || sit == s.begin() ? NIE : -- sit;}
//返回指向sit的前一个元素的iteratorinline void update(int i) {//维护并关注set尾部值开始变大的元素 auto back(-- s.end());if (p == s.begin()) return;auto P(pre(p));if (p == NIE && (* back).a + (* back).index + 1 <= i) p = back, P = pre(p);else if (P != NIE && ((* P).a + (* P).index + 1 <= i)) p = P, P = pre(p);if (P != NIE && (Get(p, i) >= Get(P, i))) {s.erase(p ++);if (p == s.end()) p = NIE;}
}inline void maintain(int i) {//维护整个setauto temp(s.insert(node(a[i + 1], f[i], i)));if (!temp.second) return;auto Iterator(temp.first);auto Pre(pre(Iterator));if (Pre != NIE && Get(Pre, i) <= Get(Iterator, i)) {//当前插入的元素是无用的s.erase(Iterator), update(i); return;}auto back(-- s.end());if (Iterator == back) {update(i); return;}auto sit(++ Iterator);-- Iterator;int val(Get(Iterator, i));while (sit != back)//往后删除无用元素，如果是指针p指向的元素要小心，否则内存崩溃if (sit == p && Get(sit, i) >= val)++ sit, s.erase(p ++);else if (Get(sit, i) >= val) s.erase(sit ++);else break;if (back == p && Get(back, i) >= val) s.erase(p), p = NIE;else if (Get(back, i) >= val) s.erase(back);update(i);
};int main() {int n(read());for (int i(1); i <= n; ++ i) a[i] = read();int v(0);for (register int i(1); i <= n; ++ i) if (v == 0) v = a[i]; else -- v;//啊这，要特判不然95qwqif (v == 0) {putchar('0'); return 0;}f[0] = 0;for (register int i(1); i <= n; ++ i) {maintain(i - 1);f[i] = Get2(-- s.end(), i);}printf("%d", f[n]);return 0;
}