題意： 給出一個長度為n的數列，要求從中取出不超過m段連續的數，使其和最大。 n<=100000
解題方法： 這題可以把一段同號的數并成一個數，那么就變成了一個正負交替的序列，然后把頭尾的負數去掉。 有一種想法就是把所有的正值都加起來，然后把所有數的絕對值加進優先隊列，每次去一個最小的出來然后減掉，最后的即為答案。 為什么是正確的呢？因為如果減去的值在原數列中為正則相當于不要這個數，否則就相當于選了這個負數然后把兩邊的正值合并起來。 但有一個問題，就是若選了一個數那么其兩邊的數就必定不能被選，那么就轉換成了數據備份了。 題解參考的hzwer大牛的，orz
//bzoj 1150#include <bits/stdc++.h>using namespace std;const int inf = 0x7fffffff;const int maxn = 100010;typedef long long LL;inline int read(){ char ch=getchar(); int f=1,x=0; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();} return x*f;}inline LL llread(){ char ch=getchar(); LL f=1,x=0; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();} return x*f;}struct node{ int pos, v; node(){} node(int pos, int v) : pos(pos), v(v) {} bool Operator < (const node &rhs) const{ return v > rhs.v; }};PRiority_queue <node> que;int n, m, a[maxn], b[maxn], L[maxn], R[maxn], vis[maxn];int main(){ n = read(); m = read(); for(int i = 1; i <= n; i++) b[i] = read(); int n1 = 1; a[1] = b[1]; for(int i = 2; i <= n; i++){ if(a[n1] <= 0 && b[i] <= 0) a[n1] += b[i]; else if(a[n1] >= 0 && b[i] >= 0) a[n1] += b[i]; else a[++n1] = b[i]; } if(a[n1] <= 0) n1--; if(a[1] <= 0){ for(int i = 1; i < n1; i++){ a[i] = a[i+1]; } n1--; } n = n1; int cnt = 0, ans = 0; for(int i = 1; i <= n; i++){ if(a[i] > 0){ cnt++; ans += a[i]; } que.push(node(i, abs(a[i]))); a[i] = abs(a[i]); L[i] = i - 1; R[i] = i + 1; } R[n] = L[1] = 0; if(cnt <= m){ printf("%d/n", ans); return 0; } m = cnt - m; for(int i = 1; i <= m; i++){ node now = que.top(); que.pop(); while(vis[now.pos] && !que.empty()) {now = que.top(); que.pop();} if(vis[now.pos]) break; ans -= now.v; if(que.empty()) break; int x = now.pos; if(!R[x]){ vis[x] = 1; vis[L[x]] = 1; R[L[L[x]]] = 0; } else if(!L[x]){ vis[x] = 1; vis[R[x]] = 1; L[R[R[x]]] = 0; } else{ node nxt; vis[L[x]] = vis[R[x]] = 1; nxt.v = a[x] = a[R[x]] + a[L[x]] - a[x]; nxt.pos = x; que.push(nxt); if(R[R[x]]) L[R[R[x]]] = x; if(L[L[x]]) R[L[L[x]]] = x; L[x] = L[L[x]]; R[x] = R[R[x]]; } } printf("%d/n", ans); return 0;}新聞熱點
疑難解答
