[C++] 純文本查看 復制代碼
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
long long ans=0;
vector<int> stk;
stk.reserve(n);
for(int i=0;i<n;i++)
{
int now;
scanf("%d",&now);
while(stk.size()>0 && now>=stk.back())
{
stk.pop_back();
if(!stk.empty())
ans+=min(stk.back(),now);
else
ans+=now;
}
stk.push_back(now);
}
for(int i=0;i<stk.size()-1;i++)
ans+=stk;
printf("%lld\n",ans);
}
[C++] 純文本查看 復制代碼
#include<cstdio>
using namespace std;
int n;
int a[1000010];
long long sol(int s,int e,int b)
{
if(s==e+1)
return 0;
if(s==e)
return b;
int m=s;
for(int i=s;i<=e;i++)
if(a>a[m])
m=i;
return sol(s,m-1,a[m])+sol(m+1,e,a[m])+b;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a);
printf("%lld\n",sol(0,n-1,0));
}
[C++] 純文本查看 復制代碼
#include<cstdio>
#include<algorithm>
using namespace std;
int in[1000000];
int N;
typedef long long ll;
typedef pair<int,int> pll;
pll sq[2200000];
void modify(int i,int v,int L,int R,int id)
{
if(L==R){
sq[id]={v,i};
return ;
}
int M = (L+R)/2;
if(i<=M)modify(i,v,L,M,id*2);
else modify(i,v,M+1,R,id*2+1);
sq[id] = max(sq[id*2],sq[id*2+1]);
}
pll max(int l,int r,int L,int R,int id)
{
if(l<=L&&R<=r)
return sq[id];
if(r<L||R<l)
return {0,0};
int M = (L+R)/2;
return max( max(l,r,L,M,id*2),max(l,r,M+1,R,id*2+1) );
}
#define rmq 0,N-1,1
ll solve(int L,int R)
{
if(L==R)return 0;
if(L+1==R){
return max(in[L],in[R]);
}
ll cost = 0;
pll mv = max(L,R,rmq);
ll mid = mv.second;
ll val = mv.first;
if( L < mid )
{
cost+=solve(L,mid-1);
cost+=val;
}
if( mid < R )
{
cost+=solve(mid+1,R);
cost+=val;
}
return cost;
}
int main()
{
ll sum=0;
bool inc = true;
bool dec = true;
scanf("%d",&N);
for(int i=0;i<N;++i)
{
scanf("%d",&in);
modify(i,in,rmq);
sum+=in;
if(i){
if(in[i-1]<in)dec=false;
if(in[i-1]>in)inc=false;
}
}
if(!inc && !dec)
printf("%lld\n",solve(0,N-1));
else
printf("%lld\n",sum-*min_element(in,in+N));
}