SRM476 Div2 Hard(1000) SubAnagrams

TopCoder

SubAnagrams

n=|X|として、O(n3)ならば間に合う。動的計画法。numi,jをX[0..j]からX[i..j]を切り出したときのX[0..j]の最大分割数、tをX[t..i-1]がX[i..j]の部分グラフとなる最小のtとすると、

numi,j = mint≦k≦i-1(numk,i-1+1)。

#include <string>
#include <vector>
#include <numeric>

using namespace std;

class SubAnagrams
{
public:
    int maximumParts( vector <string> suppliedWord );
};

int SubAnagrams::maximumParts( vector <string> suppliedWord )
{
    string X = accumulate( suppliedWord.begin(), suppliedWord.end(), string() );
    int n = (int)X.length();

    //  X[0..j]からX[i..j]を切り出したときのX[0..j]の最大分割数
    vector<vector<int> > number( n, vector<int>( n ) );
    number[0] = vector<int>( n, 1 );

    for ( int i=1; i<n; i++ )
    for ( int j=i; j<n; j++ )
    {
        //  X[t..i-1]がX[i..j]の部分アナグラムになる最小のt
        int t;

        int a[26] = { 0 };
        for ( int k=i; k<=j; k++ )
            a[X[k]-'A']++;

        int b[26] = { 0 };
        for ( t=i-1; t>=0; t-- )
            if ( ++b[X[t]-'A'] > a[X[t]-'A'] )
                break;
        t++;

        for ( int k=t; k<i; k++ )
            if ( number[k][i-1] > 0 )
                number[i][j] = max( number[i][j], number[k][i-1]+1 );
    }

    int ans = 0;
    for ( int i=0; i<n; i++ )
        ans = max( ans, number[i][n-1] );
    return ans;
}