学步园

D2 1000p PalindromeFactory

邮局问题。设Dp[i][j]为从串[i,j]得到回文串的最小步数，然后进行两种操作：删除一个字符、删除两个字符。

class PalindromeFactory<br /> {<br /> string str;<br /> int dp[50][50];</p> <p> int get ( int l, int r )<br /> {<br /> if ( l == r || l == r - 1 && str[l] == str[r] )<br /> return dp[l][r] = 0;<br /> if ( l == r - 1 && str[l] != str[r] )<br /> return dp[l][r] = 1;<br /> if ( dp[l][r] != -1 )<br /> return dp[l][r];<br /> int &res = dp[l][r];<br /> if ( str[l] == str[r] )<br /> res = get ( l + 1, r - 1 );<br /> else<br /> res = get ( l + 1, r - 1 ) + 1;<br /> res = min ( res, get ( l + 1, r ) + 1 );<br /> res = min ( res, get ( l, r - 1 ) + 1 );<br /> return res;<br /> }<br /> public:<br /> int getEditDistance(string initial)<br /> {<br /> str = initial;<br /> memset ( dp, 0xff, sizeof ( dp ) );<br /> int ret = get ( 0, str.size () - 1 );</p> <p> int i, j, n = str.size ();<br /> for ( i = 0; i < n; i ++ )<br /> for ( j = i + 1; j < n; j ++ )<br /> {<br /> memset ( dp, 0xff, sizeof ( dp ) );<br /> swap ( str[i], str[j] );<br /> ret = min ( ret, get ( 0, n - 1 ) + 1 );<br /> swap ( str[j], str[i] );<br /> }<br /> return ret;<br /> }<br /> }

D1 250p  PalindromePhrases

所求解其实就是二进制表达时1的个数。

D1 500p PalindromePhrases

相当有技术含量的DP。

考虑ab, edcba, cd这样的情况，从外向内构造解。

ab和edcba中的ba配对之后，还剩下edc，可以和cd配对。由于只有13个元素，首先考虑到的是bitmask。确定组合后剩下的字符可以做一状态。由于配对有两个方向：如例子中的cd是正方向配对，而edcba是反方向配对，因此将方向作为状态。总状态即为：DP(string 字符串, int 方向, int bitmask)

 #define MP make_pair</p> <p>class PalindromePhrases<br /> {<br /> map < pair < string, int >, long long > m[1 << 13];<br /> vector < string > w[2];<br /> int n;</p> <p> bool isP ( const string &s ) // palindromic<br /> {<br /> int i = 0, j = s.size () - 1;<br /> while ( i < j && s[i] == s[j] )<br /> i ++, j --;<br /> return i >= j;<br /> }<br /> int getPrefix ( const string &a, const string &b )<br /> {<br /> int i, ret = 0;<br /> for ( i = 0; i < a.size () && i < b.size (); i ++ )<br /> {<br /> if ( a[i] == b[i] )<br /> ret ++;<br /> else<br /> break;<br /> }<br /> return ret;<br /> }</p> <p> long long get ( const string &ex, int r, int used )<br /> {<br /> //printf ( "%s %d %d/n", ex.c_str (), r, used );<br /> if ( used == ( 1 << n ) - 1 )<br /> {<br /> //printf ( "%s %d %d/n", ex.c_str (), r, used );<br /> //printf ( "back %d/n/n", isP ( ex ) );<br /> return isP ( ex );<br /> }<br /> pair < string, int > key = MP ( ex, r );<br /> if ( m[used].count ( key ) )<br /> {<br /> //printf ( "%s %d %d/n", ex.c_str (), r, used );<br /> //printf ( "%lld/n/n", m[used][key] );<br /> return m[used][key];<br /> }<br /> long long int &res = m[used][key];<br /> res = 0;<br /> if ( isP ( ex ) )<br /> res = 1;<br /> int i;<br /> for ( i = 0; i < n; i ++ )<br /> if ( ( ( 1 << i ) & used ) == 0 )<br /> {<br /> int wlen = w[r][i].size ();<br /> int plen = getPrefix ( w[r][i], ex );<br /> if ( plen != wlen && plen != ex.size () )<br /> continue;<br /> int t;<br /> if ( plen == wlen )<br /> {<br /> res += ( t = get ( ex.substr ( plen ), r, ( 1 << i ) | used ) );<br /> }<br /> else<br /> {<br /> res += ( t = get ( w[r][i].substr ( plen ), 1 - r,<br /> ( 1 << i ) | used ) );<br /> }<br /> }<br /> //printf ( "%s %d %d/n", ex.c_str (), r, used );<br /> //printf ( "%d/n/n", res );<br /> return res;<br /> }<br /> }