問題文: 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; }