Topcoder SRM 533 Div1(Easy) CasketOfStar

https://community.topcoder.com/stat?c=problem_statement&pm=11781

n <= 50, w[i] <= 1000

n 이 주어지고 n개의 정수 w[i] 가 주어진다.

n개의 칸이 있는데 특정 순서로 칸들을 지워서 점수를 최대로 하는 문제이다.

양쪽 두 칸은 지울 수 없다.

k번째 칸을 지울 때 얻을 수 있는 점수는 w[k-1] * w[k+1] 이고 k를 지웠으면

번호를 0부터 다시 매긴다. 이것을 반복하여 점수를 최대로 지우는 것이다.

일단 두가지 방법으로 풀어 보았는데 처음엔 O(n^3) 풀이를 떠올렸다.

dp[prv][l][r] : 직전 수가 prev, 현재 보는수가 l, 오른쪽 끝이 r 일때 최대 점수

라고 보면 맨 왼쪽 칸부터 점수를 계산을 하며

각 부분문제를 구할 때 얼마만큼 건너뛸지를 정하게 되는데(0 포함)

현재 위치를 l 이라고 할 때 이 위치다음부터

1. 연속된 k개의 칸을 현재의 칸보다 먼저 없애고(재귀적으로 계산 가능),

2. 그다음으로 현재칸을 없애고

3. 그 다음으로 연속된 k개의 칸 이후 부터 오른쪽 경계까지의 칸들을 없앤다(이것도 재귀적으로 계산 가능)

는 아이디어이다.

이렇게 하면 각 칸을 지울 때 왼쪽 칸과 오른쪽 칸을 강제하고 넘어가기 때문에 현재 칸을

다음에 나오는 칸들 보다 나중에 지울 것이라고 하더라도 미리 점수를 계산하고 넘어갈 수가 있다.

대신 이놈을 먼저 계산했으니 그에 대한 정보를 제한으로서 r로 넘기고 이전 칸의 정보를 prv로 넘기는것이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int dp[53][53][53];
int w[53];
class CasketOfStar {
    public:
        int go(int prev, int l, int r){
            if(l == r) return 0;
            int& cache = dp[prev][l][r];
            if(cache != -1) return cache;
            int ret = 0;
            for(int i = l + 1; i <= r; i++){
                ret = max(ret, w[prev] * w[i] + go(l, l + 1, i) + go(prev, i, r));
            }
            return cache = ret;
        }
    int maxEnergy(vector<int> weight) {
        memset(dp,-1,sizeof(dp));
        int n = (int)weight.size();
        for(int i = 0 ; i < n; i++) w[i] = weight[i];
        return go(0, 1, n-1);
    }
};

그런데 조금만 더 생각해 보면 굳이 앞에서 부터 계산하여 불필요한 정보를 넘겨줄 필요가 없다.

dp[l][r] : (l, r) 의 셀을 지울 때 최대 점수

라고 부분 문제를 정의하면

로 놓고 하면 (l, r) 내의 cell 중 마지막에 지워지는 놈 k를 고정하면

두개의 부분 문제 dp[l][k] + dp[k][r] 로 나뉘어 진다. 고로 점화식은

dp[l][r] = max(dp[l][k] + dp[k][r])(l < k < r) + w[l] * w[r] 가 되는 것이다.

이렇게하면 O(n^2) 에 풀 수가 있다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
int dp[53][53];
int w[53];
class CasketOfStar {
    public:
        int go(int l, int r){
            if(l + 1 == r) return 0;
            int& cache = dp[l][r];
            if(cache != -1) return cache;
            int ret = 0;
            for(int i = l + 1; i <= r - 1; i++) ret = max(ret, go(l, i) + go(i, r));
            return cache = ret + w[l] * w[r];
        }
    int maxEnergy(vector<int> weight) {
        memset(dp,-1,sizeof(dp));
        int n = (int)weight.size();
        for(int i = 0 ; i < n; i++) w[i] = weight[i];
        return go(0, n - 1);
    }
};