SRM566 Div2 Medium(500) PenguinPals

PenguinPals

最適なペンギンの組合わせがあったとすると、ペンギンの並びをどこか1箇所で切って直線にできる。ペンギンが直線に並んでいたとすると、最多の組数は動的計画法で求められる。各区間内のペンギンでの最多の組数を覚えておけばよい。

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

class PenguinPals{public:
int findMaximumMatching( string colors )
{
    int n = (int)colors.length();
    int ans = 0;

    for ( int i=0; i<n; i++ )
    {
        vector<vector<int> > T(n,vector<int>(n));
        for ( int j=1; j<n; j++ )
        for ( int k=0; k<n-j; k++ )
        {
            int t = colors[k]==colors[k+j] ? 1 : 0;
            T[k][k+j] = max( T[k][k+j], t );
            for ( int l=k+2; l<k+j; l++ )
                T[k][k+j] = max( T[k][k+j], t+T[k+1][l] );
            for ( int l=k+1; l<k+j-1; l++ )
                T[k][k+j] = max( T[k][k+j], t+T[l][k+j-1] );
            for ( int l=k+1; l<k+j; l++ )
                T[k][k+j] = max( T[k][k+j], T[k][l]+T[l+1][k+j] );
        }

        ans = max( ans, T[0][n-1] );

        colors = colors.substr(1) + colors[0];
    }

    return ans;
}};