SRM-424 600pt: StrengthOrIntellect

keyword

メモ化再帰　C++

問題概要

ミッションがN(<50)個ある。各ミッションには必要知性と必要体力とボーナスポイントが割り振られている。パラメータは最初(1,1)から始まり、必要知性と必要体力のいずれかを満たしていればそのミッションをクリアし、ボーナスポイントを自分のパラメータに割り振ることができる。最大でいくつのミッションをクリアできるか求める問題。必要知性と必要体力の最大値はM=1000。

解法

memo[知性][体力]としてメモ化再帰で解く。ただし、素朴にやるとO(M^2 * (M+N))となってTLEする。ここで、知性や体力を中途半端に割り振る必要がないことに着目して、座標圧縮風に知性か体力のどっちかは必要体力か必要知性に現れる数値になる様にする。こうすると計算量はO(M*N^2)に落ちる。

感想

2回再送信してやっと通った自分が言うのも何だけど今の基準じゃ600ptにはならない気がする。

vector<int> S, I, P;
int N;
int dp[1002][1002];
int MY, MX;

int numberOfMissions(vector <int> strength, vector <int> intellect, vector <int> points) {
    S = strength;
    I = intellect;
    P = points;
    N = SZ(strength);
    MY = *max_element(ALL(intellect));
    MX = *max_element(ALL(strength));
    for(int i=0; i<=1000; i++){
        for(int j=0; j<=1000; j++){
            dp[i][j] = -1;
        }
    }
    return rec(1,1);
}

int rec(int x, int y){
    if(dp[x][y]!=-1) return dp[x][y];
    int up = 0, ret = 0;
    for(int i=0; i<N; i++){
        if(x >= S[i] || y >= I[i]){
            ret++;
            up += P[i];
        }
    }
    up -= x + y - 2;
    if(!up) return ret;
    for(int i=0; i<N; i++){
        if(x <= S[i] && x + up >= S[i]){
            int nx = S[i], ny = y + up - (S[i] - x);
            if(ny >= MY || nx >= MX) return dp[x][y] = N;
            ret = max( ret, rec(nx,ny) );
        }
    }
    for(int i=0; i<N; i++){
        if(y <= I[i] && y + up >= I[i]){
            int nx = x + up - (I[i] - y), ny = I[i];
            if(ny >= MY || nx >= MX) return dp[x][y] = N;
            ret = max( ret, rec(nx,ny) );
        }
    }
    return dp[x][y] = ret;
}