AtCoder ARC #211 : C - Forest

嵌りすぎた…。
https://atcoder.jp/contests/arc211/tasks/arc211_c

問題

Nマスが並んでおり、一部は埋まっている。
また、各セルiにはパラメータR[i]が設定されている。

ここで、可能な限り以下を行う。

• 両端以外で1個以上埋まったマスを含む区間[i,j]を選ぶ。スコアR[i]+R[j]を得た後、埋まったマスが空になる。

総スコアを最大化するため、初手としてあり得るのは何通りか。

解法

初手は、Rのうち最大値が書かれたマスを空にできるような処理となる。
よってそのような処理を列挙しよう。

int N;
string S;
ll A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	int NE=0;
	vector<pair<int,int>> V;
	
	FOR(i,N) {
		cin>>A[i];
		if(i==0||S[i]!=S[i-1]) {
			V.push_back({0,0});
		}
		if(A[i]>V.back().first) V.back()={A[i],0};
		if(A[i]==V.back().first) V.back().second++;
	}
	if(S[0]=='#') V.erase(V.begin());
	if(S.back()=='#') V.pop_back();
	int ma=0;
	FORR2(a,b,V) ma=max(ma,a);
	ll ret=0;
	for(i=0;i<V.size()-2;i+=2) {
		if(max({V[i].first,V[i+1].first,V[i+2].first})==ma) {
			ret+=1LL*V[i].second*V[i+2].second;
		}
	}
	cout<<ret<<endl;
	
	
}

まとめ

これでてこずったの良くないな…。