http://codeforces.com/contest/442/problem/C
The meaning of the question is very easy. Basically, there must be some pits. Look at the question cases, starting from the third to the third If you look at the two cases without concavity, if you write a few more and draw more, you will find that all but the two largest numbers can be obtained, and then there is the concave case. The concave case is definitely the only one. , remove the middle number to get a value, but what should I do if there is a combination of concave and convex? Let me guess, solve the concave ones one by one first, generate a sequence without concavities and then process it, and then just test the first case , found that the answer was correct, so I greedily typed one
For concave cases, you can use the stack. After processing, for non-concave cases, you can directly sort everything except the largest two numbers.
#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define eps 1e-8const int inf = 0xfffffff;const ll INF = 1ll<<61;using namespace std;//vector<pair<int,int> > G;//typedef pair<int,int > P;//vector<pair<int,int> > ::iterator iter;////map<ll,int >mp;//map<ll,int >::iterator p;int n;int num[1000000 + 5];stack<int > s;ll ans; void init() { memset(num,0,sizeof(num)); while(!s.empty())s.pop(); ans = 0ll;}bool input() { while(scanf("%d",&n) == 1) { for(int i=0;i<n;i++) scanf("%d",&num[i]); return false; } return true;}void cal() { bool flag = false; s.push(num[0]); for(int i=1;i<n;i++) { if(num[i] <= s.top()) {s.push(num[i]);flag = true;continue;} if(num[i] >= s.top() && flag) { s.pop(); ans += min(num[i],s.top()); if(num[i] <= s.top())flag = true; else { while(true) { int tmp = s.top(); s.pop(); if(s.empty()) { s.push(tmp); break; } if(tmp > s.top() || num[i] < tmp) { s.push(tmp); break; } if(num[i] >= tmp)ans += min(s.top(),num[i]); } } if(num[i] <= s.top())flag = true; else flag = false; s.push(num[i]); continue; } s.push(num[i]); } memset(num,0,sizeof(num)); int cnt = 0; while(!s.empty()) { num[cnt++] = s.top(); s.pop(); } sort(num,num+cnt); for(int i=0;i<cnt-2;i++) ans += num[i];}void output() { printf("%I64d\n",ans);}int main() { while(true) { init(); if(input())return 0; cal(); output(); } }
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
