BOJ 16238 - 독수리

BOJ 16238 - 독수리

사수아탕 류 문제의 기본적인 아이디어라고 볼 수 있겠다.

항상 독수리는 한 방향으로만 날아도 된다는 점을 관찰한다.

독수리가 먹을 양을 $0 \sim N$ 마리로 정해두고 현재 $X$ 마리라면 가장 큰 $X$마리만 먹으면 된다.

만약 $X$ 마리 모두 $X$ 이상이 아니라면 어떤건 먹기 전에 도망가기 때문에 더 이상 탐색을 할 필요는 없다.

$DP$로도 풀 수 있다.

$DP[i][j]=i$ 번 째 칸까지 $j$ 번 양을 먹었을 때 최대값이라고 정의해두자.

그럼 정답은 $\text{Max}_{j=0}^N DP[N][j]$ 이다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   a.insert(a.begin(), 0);
   a.pb(0);

   int ans = 0;
   // i 번째에 j 일에 도착했을 때 최대값
   vvi dp(n + 2, vi(n + 2));
   vi mx(n + 2);
   for (int i = 1; i <= n; i++) {
      for (int j = i; j >= 1; j--) {
         int lose = j - 1;
         int gain = max(0ll, a[i] - lose);

         dp[i][j] = gain + mx[j - 1];
         maxa(mx[j], dp[i][j]);
      }
   }
   maxa(ans, maxe(mx));
   cout << ans;
}