AOJ 0551 Icicles

問題文: Icicles | Aizu Online Judge

なんか昔プライオリティキューを使って解くというのを見たせいでまったく解けなかった。頭悪い。。。

プライオリティキュー忘れて適当にメモ化再帰したら解けたっていう...。

しかもこっちの方が短いし早い気が。再帰だから遅いのかもしれないけど。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF (1<<29)

int data[100002] , memo[100002];
int n,L;
int recurse(int n){
	if(~memo[n]) return memo[n];

	int ans = 0;
	if(data[n+1] > data[n]) ans = max( ans , recurse(n+1) );
	if(data[n-1] > data[n]) ans = max( ans , recurse(n-1) );
	
	return memo[n] = ans + (L - data[n]);
}
int main(){
	memset(memo,-1,sizeof(memo));
	cin >> n >> L;
	for(int i = 1 ; i <= n ; i++) cin >> data[i];
	int ans = 0;
	for(int i = 1 ; i <= n ; i++){
		ans = max<int>( ans , recurse(i) ); 
	}
	cout << ans << endl;
}