SRM 596 D2 L2：ColorfulRoad，dp

题目：http://community.topcoder.com/stat?c=problem_statement&pm=12837

类似于弗洛伊德最短路径算法思想。

代码：

#include <algorithm>
#include <iostream>
#include <sstream>

#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>

using namespace std;


#define CHECKTIME() printf("%.2lf\n", (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 <int> 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 ************************/

SRM 596 D2 L2：ColorfulRoad，dp

原文：http://blog.csdn.net/xzz_hust/article/details/19051637