SRM453.5 Div1 Medium(450) PlanarGraphShop

TopCoder

PlanarGraphShop

動的計画法。c 個のグラフで n コインとなるなら、c+1 個のグラフの組み合わせで n+1, c+8, c+9, c+27, ……コインを作れる。
グラフが平面グラフとなる条件はWikipediaより、


Gが平面的グラフならば、|E(G)|≦3|V(G)|-6。ただし、|V(G)|≧3。

X=2 のときは Y≦1、X=1 のときは Y=0。

#include <vector>

using namespace std;

class PlanarGraphShop
{
public:
    int bestCount( int N );
};

int PlanarGraphShop::bestCount( int N )
{
    vector<int> count( N+1, INT_MAX );
    count[0] = 0;

    for ( int c=0; count[N]==INT_MAX; c++ )
    {
        for ( int i=0; i<=N; i++ )
        if ( count[i] == c )
        {
            for ( int X=1; i+X*X*X<=N; X++ )
            for ( int Y=0; i+X*X*X+Y*Y<=N; Y++ )
            {
                if ( X == 1  &&  Y > 0  ||
                     X == 2  &&  Y > 1  ||
                     X > 2   &&  Y > 3*X-6 )
                    break;

                count[i+X*X*X+Y*Y] = min( count[i+X*X*X+Y*Y], c+1 );
            }
        }
    }

    return count[N];
}