SRM497 Div1 Medium(550) CssRules - kusano

動的計画法。あるタグの子孫を正しく塗るために必要なCSS規則の個数は、そのタグの祖先によって定められたb,u,iタグの色のみに依存するので、それを覚えておく。

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

struct TAG
{
    char        tag;
    int         color;
    vector<TAG> child;
    vector<int> memo;
};

vector<TAG> load( string xhtml, int &p )
{
    const string color[] = { "none", "black", "blue", "gray",
                             "green", "red", "white", "yellow" };

    vector<TAG> tag;

    while ( p<(int)xhtml.length() && xhtml[p+1]!='/' )
    {
        TAG t;
        t.tag = xhtml[p+1];
        while ( xhtml[p]!=':' )
            p++;
        p++;
        string c;
        while ( xhtml[p]!='\'' )
            c += xhtml[p++];
        t.color = find(color,color+8,c) - color;
        p += 2;
        t.child = load(xhtml,p);
        t.memo = vector<int>(8*8*8,-1);
        p += 4;
        tag.push_back(t);
    }
    
    return tag;
}

int DP( TAG &tag, int tb, int tu, int ti )
{
    int n = (tb*8+tu)*8+ti;
    if ( tag.memo[n] >= 0 )
        return tag.memo[n];

    int ans = 99999999;

    for ( int b=min(tb,1); b<8; b++ )
    for ( int u=min(tu,1); u<8; u++ )
    for ( int i=min(ti,1); i<8; i++ )
    {
        //  #id tagName
        int c = 0;
        if ( b!=tb )  c++;
        if ( u!=tu )  c++;
        if ( i!=ti )  c++;

        //  #id
        if ( tag.tag=='b' && tag.color!=tb )  c++;
        if ( tag.tag=='u' && tag.color!=tu )  c++;
        if ( tag.tag=='i' && tag.color!=ti )  c++;

        for ( int j=0; j<(int)tag.child.size(); j++ )
            c += DP( tag.child[j], b, u, i );
        
        ans = min( ans, c );
    }

    return tag.memo[n] = ans;
}

class CssRules{public:
int getMinimalCssRuleCount( vector <string> xhtml )
{
    string x = accumulate(xhtml.begin(),xhtml.end(),string());
    int p = 0;
    vector<TAG> tag = load(x,p);

    int ans = 0;
    for ( int i=0; i<(int)tag.size(); i++ )
        ans += DP( tag[i], 0, 0, 0 );
    return ans;
}};