SRM563 Div2 Hard(1000) SpellCardsEasy

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

#include <vector>
using namespace std;

class SpellCardsEasy{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-l; 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][l2][r2] );
            }
        }

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

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

    return ans;
}};