SRM566 Div2 Medium(500) 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; }};