相当于是在求最短路，dp之。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int INF = 1 << 29; 7 const int N = 21; 8 char road[N]; 9 int cost[N]; 10 11 void init() 12 { 13 cost[0] = 0; 14 for ( int i = 1; i < N; i++ ) cost[i] = INF; 15 } 16 17 bool check( int i, int j ) 18 { 19 if ( road[i] == 'R' && road[j] == 'G' ) return true; 20 if ( road[i] == 'G' && road[j] == 'B' ) return true; 21 if ( road[i] == 'B' && road[j] == 'R' ) return true; 22 return false; 23 } 24 25 int main () 26 { 27 int t; 28 scanf("%d", &t); 29 while ( t-- ) 30 { 31 scanf("%s", road); 32 int len = strlen(road); 33 init(); 34 for ( int i = 0; i < len - 1; i++ ) 35 { 36 for ( int j = i + 1; j < len; j++ ) 37 { 38 if ( check( i, j ) ) 39 { 40 int tmp = cost[i] + ( j - i ) * ( j - i ); 41 if ( tmp < cost[j] ) cost[j] = tmp; 42 } 43 } 44 } 45 if ( cost[len - 1] == INF ) cost[len - 1] = -1; 46 printf("%d ", cost[len - 1]); 47 } 48 return 0; 49 }