题目链接：http://codeforces.com/problemset/problem/442/C
题目大意：一个数列，有n个元素。你可以做n-2次操作，每次操作去除一个数字，并且得到这个数字两边相邻的数最小的分数。问你最多得到多少分。
将高度绘图，去除V的情况。
用单调栈优化，每个元素进栈一次，出栈一次。线性时间。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include <set> 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include <string> 17 #include 18 using namespace std; 19 #define PB push_back 20 #define MP make_pair 21 #define SZ size() 22 #define ST begin() 23 #define ED end() 24 #define CLR clear() 25 #define ZERO(x) memset((x),0,sizeof(x)) 26 typedef long long LL; 27 typedef unsigned long long ULL; 28 typedef pair<int,int> PII; 29 const double EPS = 1e-8; 30 31 const int MAX_N = 5*1e5+100; 32 int n,top; 33 LL st[MAX_N]; 34 35 int main() { 36 cin >> n; 37 top = -1; 38 LL ans = 0; 39 for(int i=0;i){ 40 LL x; 41 cin >> x; 42 while( top>=1 && st[top]1]&&st[top]<=x ){ 43 ans += min(st[top-1],x); 44 top--; 45 } 46 st[++top] = x; 47 } 48 sort(st,st+top+1); 49 for(int i=0;i1;i++) ans += st[i]; 50 cout < endl; 51 return 0; 52 }
[CF442C] Artem and Array (贪心＋单调栈优化)
京公网安备 11010802041100号