类似于弗洛伊德最短路径算法思想。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) /*************** Program Begin **********************/ int dp[20][20]; class ColorfulRoad { public: int getMin(string road) { int res = 0; int n = road.size(); vector v; for (int i = 0; i < n; i++) { if (road[i] == 'R') { v.push_back(0); } else if (road[i] == 'G') { v.push_back(1); } else { v.push_back(2); } } memset(dp, -1, sizeof(dp)); for (int len = 1; len <= n - 1; len++) { for (int i = 0; i <= n - len - 1; i++) { int & ans = dp[i][i+len]; if ( (v[i] + 1) % 3 == v[i+len] ) { ans = len * len; } for (int j = i + 1; j < i + len; j++) { if (dp[i][j] == -1 || dp[j][i+len] == -1) { continue; } if (ans == -1) { ans = dp[i][j] + dp[j][i+len]; } ans = min(ans, dp[i][j] + dp[j][i+len]); } } } res = dp[0][n-1]; return res; } }; /************** Program End ************************/