http://acm.pku.edu.cn/JudgeOnline/problem?id=1141
dp
参考沈云付的书。。。。
#include<iostream> #include<string> using namespace std; #define MAX 101 int main() { //freopen("in.txt", "r", stdin); int dp[MAX][MAX]; //第i个字符到第j个字符需要添加的最少括号数。 string ans[MAX][MAX]; //str的第i个字符到第j个字符经过添加dp[i][j]个括号后得到的正则串 char str[MAX]; int i, j, k, len; //注意：有空行。 while(gets(str)) { len = strlen(str); for(i=0; i<len; i++) for(j=i; j<len; j++) { ans[i][j] = ""; dp[i][j] = 0x7ffffff; } for(i=len-1; i>=0; i--) { for(j=i; j<len; j++) { if(i == j) { dp[i][j] = 1; if(str[i] == '(' || str[i] == ')') ans[i][j] = "()"; else ans[i][j] = "[]"; } else { if(j > i) { if((str[i] == '(' && str[j] == ')') || (str[i] == '[' && str[j] == ']')) { if(dp[i][j] > dp[i+1][j-1]) { dp[i][j] = dp[i+1][j-1]; ans[i][j] = str[i] + ans[i+1][j-1] + str[j]; } } } } for(k=i; k<j; k++) if(dp[i][k] + dp[k+1][j] < dp[i][j]) { dp[i][j] = dp[i][k] + dp[k+1][j]; ans[i][j] = ans[i][k] + ans[k+1][j]; } } } printf("%s/n", ans[0][len-1].c_str()); } return 0; }
相关资源：Office2016专业增强版中文免费正式版(附安装教程)64位