SRM563 Div1 Medium(500) SpellCards - kusano

動的計画法。位置pからl枚のカードを使いr枚のカードを残す場合の最高ダメージを覚えてく。O(n⁵)だけど、for(x=0;x

#include <vector>
using namespace std;

class SpellCards{public:
int maxDamage( vector <int> level, vector <int> damage )
{
    int n = (int)level.size();

    //  [p][l][r]: 位置pからl枚のカードを使いr枚のカードを残す場合の最高ダメージ
    static int T[64][64][64];
    for ( int i=0; i<64*64*64; i++ )
        T[0][0][i] = 0;

    for ( int l=1; l<=n; l++ )
    for ( int p=0; p<n; p++ )
    {
        for ( int l1=1; l1<l; l1++ )
        {
            int l2 = l-l1;
            for ( int r1=0; r1<=l1; r1++ )
            for ( int r2=0; r2<=l2; r2++ )
            {
                int r = r1+r2;
                T[p][l][r] = max( T[p][l][r], T[p][l1][r1]+T[(p+l1)%n][l2][r2] );
            }
        }

        if ( level[p]<=l )
            T[p][l][0] = max( T[p][l][0], damage[p]+T[(p+1)%n][l-1][level[p]-1] );
    }

    int ans = 0;
    for ( int p=0; p<n; p++ )
        for ( int r=0; r<=n; r++ )
            ans = max( ans, T[p][n][r] );

    return ans;

}};

として、本番中は解いたけど、実は単にlevelの合計がn以下でdamageの合計が最大になるようにカードを選べば良い。なぜなら、そのようにカードを選んだとき、少なくとも1枚は他の選んだカードを取り除かずに使えるはずで、それを繰り返せば良い。

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

class SpellCards{public:
int maxDamage( vector <int> level, vector <int> damage )
{
    int n = (int)level.size();
    vector<int> T(n+1,-99999999);
    T[0] = 0;
    for ( int i=0; i<n; i++ )
        for ( int j=n; j>=0; j-- )
            if ( j+level[i]<=n )
                T[j+level[i]] = max( T[j+level[i]], T[j]+damage[i] );
    return *max_element(T.begin(),T.end());
}};