Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-11-07

StrengthOrIntellect (SRM424 DIV1 Medium)

| 23:57 | StrengthOrIntellect (SRM424 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - StrengthOrIntellect (SRM424 DIV1 Medium) - TopCoder煮ブログ

HPとMPがあってレベルアップのときにどう振り分けるか、みたいな問題。現在の strength と intellect が分かれば、そこから余剰ポイントと通過したミッションが定まるのでそれをベースに次の状態を求めていけることに気づいた。最悪時に同じ計算を何度もやってしまっていたので、メモして高速化してみたら、難なく System Test に通った。一応ソースを貼っておこう。

#include <vector>
#include <iostream>
using namespace std;

template<class T> inline int count_bit(T n){int r=0;while(n > 0){if(n&1)r++; n>>=1;}return r;}
int visited[1001][1001];

class StrengthOrIntellect {
public:
    int N;
    vector<int> SV, IV, PV;

    int solv(int S, int I){
        S = min(S, 1000);
        I = min(I, 1000);
        if(visited[S][I]) return visited[S][I];

        int points = 0;
        long long state = 0;
        for(int i = 0; i < N; i++){
            if(S >= SV[i] || I >= IV[i]){
                state += (1LL << i);
                points += PV[i];
            }
        }
        points = points - (S + I) + 2;

        int Smin = (int)1e9, Imin = (int)1e9;
        int Sind, Iind;
        for(int i = 0; i < N; i++){
            if((state & 1LL << i)) continue;
            if(Smin > SV[i]){Smin = SV[i]; Sind = i;}
            if(Imin > IV[i]){Imin = IV[i]; Iind = i;}
        }

        int ret = 0;
        if(points > 0 && Smin <= S + points){
            ret = max(ret, solv(Smin, I));
        }
        if(points > 0 && Imin <= I + points){
            ret = max(ret, solv(S, Imin));
        }

        return visited[S][I] = max(ret, count_bit(state));
    }

    int numberOfMissions(vector <int> strength, vector <int> intellect, vector <int> points) {
        N = strength.size();
        SV = strength;
        IV = intellect;
        PV = points;
        memset(visited, 0, sizeof(visited));
        return solv(1, 1);
    }
};

ただ DP で解いたほうが全体的にすっきりとしたソースになる。

VrmanVrman2012/07/10 01:49Whoever edits and publishes these atrilces really knows what they're doing.

itdcbmoevcitdcbmoevc2012/07/10 16:018wcDPn <a href="http://xkevcdxqtevw.com/">xkevcdxqtevw</a>

nsyzafooknsyzafook2012/07/12 12:18x6IGQS <a href="http://ucopfphvzofe.com/">ucopfphvzofe</a>

gojwfkgojwfk2012/07/12 17:48qezOlz , [url=http://ezuzdkbwcdug.com/]ezuzdkbwcdug[/url], [link=http://vdrugwwanyht.com/]vdrugwwanyht[/link], http://qbsozmxyjucd.com/