1225 - 數字合併

domen111

http://tioj.ck.tp.edu.tw/problems/1225

用stack做，保持stack裡面是遞減的狀態，O(n)

[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[i];
	printf("%lld\n",ans);
}

我第一次的做法:
用divide and conquer遞迴下去，但最壞狀況(遞減數列)會是O(n^2)，所以TLE

[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[i]>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[i]);
	printf("%lld\n",sol(0,n-1,0));
}

Sylveon

針對Divide and Conquer 的補救作法，利用線段數來避免最壞狀況

隨機狀況：[tex]O(nlogn+log^4n)[/tex]
遞增減或交錯：[tex]O(nlogn+nlogn)[/tex]

[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[i]);
		modify(i,in[i],rmq);
		sum+=in[i];
		if(i){
			if(in[i-1]<in[i])dec=false;
			if(in[i-1]>in[i])inc=false;
		}
	}
	if(!inc && !dec)
		printf("%lld\n",solve(0,N-1));
	else
		printf("%lld\n",sum-*min_element(in,in+N));
}