黑书上的第一道动态规划例题

网站上还要求输出最短生成的括号序列，参考了下网上PASCAL ac的代码……

勉强过了……

dp[i][j]表示从i->j需要添加多少个括号，res[i][j]保存生成最短括号序列。表示仍然有点晕……

需要加强dp强度啊……

#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "iomanip"
#include "bitset"
#include "list"
#include "ctime"
using namespace std;

#define CC(m,what)				memset(m,what,sizeof(m))
#define FOR(i,a,b)				for( i = (a); i < (b); ++i )
#define FF(i,a)					for( i = 0; i < (a); ++i )
#define FFD(i,a)				for( i = (a)-1; i >= 0; --i )
#define FORD(i,a,b)				for( i = (a)-1; i >= (b); --i )
#define LEFT(a)					((a)<<1)
#define RIGHT(a)				(((a)<<1)+1)
#define SZ(a)					((int)a.size())
#define PP(n,m,a)				puts("---");FF(i,n){FF(j,m)printf("%10d", a[i][j]);puts("");}
#define PPc(n,m,a)				puts("---");FF(i,n){FF(j,m)printf("%c", a[i][j]);puts("");}
const double eps = 1e-11;
const double Pi = acos(-1.0);
const int	intmax = 2147483647;
const int	dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

string	s, res[110][110], temp;
int		dp[110][110];

void init() {
	int i, j;
	FF (i, SZ(s)) {
		if ( s[i] == '(' || s[i] == ')' ) res[i][i] = "()";
		else res[i][i] = "[]";
	}
	FF (i, 110) {
		FF (j, 110 ) {
			if ( i > j ) dp[i][j] = 0;
			else if ( i == j ) dp[i][j] = 1;
			else dp[i][j] = intmax;
		}
	}
}


void hexie() {
	init();
	int i, j, k, p;
	int len = SZ(s);
	FOR (i, 1, len) {
		FOR (j, 0, len-i ) {
			k = i+j;
			if ( (s[j] == '(' && s[k] == ')') || ( s[j] == '[' && s[k] == ']' ) ) {
				if ( dp[j][k] > dp[j+1][k-1] ) {
					dp[j][k] = dp[j+1][k-1];
					res[j][k] = s[j] + res[j+1][k-1] + s[k];
				}
			}
			else if ( s[j] == '(' || s[j] == '[' ) {
				if ( dp[j][k] > dp[j+1][k] + 1 ) {
					dp[j][k] = dp[j+1][k]+1;
					if ( s[j] == '(' ) 
						res[j][k] = "(" + res[j+1][k] + ")";
					else 
						res[j][k] = "[" + res[j+1][k] + "]";
				}
			} 
			else if ( s[k] == ']' || s[k] == ')' ) {
				if ( dp[j][k] > dp[j][k-1] + 1 ) {
					dp[j][k] = dp[j][k-1] + 1;
					if ( s[k] == ')' ) 
						res[j][k] = "(" + res[j][k-1] + ")";
					else 
						res[j][k] = "[" + res[j][k-1] + "]";
				}
			}
			FOR ( p, j, k ) {
				if ( dp[j][k] > dp[j][p] + dp[p+1][k] ) {
					dp[j][k] = dp[j][p] + dp[p+1][k];
					res[j][k] = res[j][p] + res[p+1][k];
				}
			}
		}
	}

//	PP(len,len,dp);

	cout << res[0][len-1] << endl;
//	cout << dp[0][len-1] << endl;
}

int main() {
	while ( getline(cin, s) ) {
		if ( SZ(s) < 1 ) { cout << s << endl; continue; }
		hexie();
	}
	return 0;
}