main.cpp

poj1411请多指教

#include <algorithm>
#include <list>
#include <vector>
#include <iostream>
#include <functional>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iomanip>
using namespace std;
#define N 101
char a[N];
int d[N][N];
int dk[N][N];
int res=200;
int n;
void myprint(int i,int j);
int main()
{
	cin >> a;
	n=strlen(a);
	for(int i=1;i<n+1;++i)
	{
		d[i][i-1] = 0;
		d[i][i] = 1;
		for(int j=i+1;j<n+1;++j)
			d[i][j]=200;
	}
	
	for(int p=1;p<n;++p)
		for(int i=1;i<n+1-p;++i)
		{
			int j=i+p;
			d[i][j] = 200;
			if(a[j-1]-a[i-1]>0  && a[j-1]-a[i-1]<3) {
				d[i][j] = min(d[i][j], d[i+1][j-1]);
				dk[i][j] = i-1;
			}
			for(int k=i;k<j;++k)
				if(d[i][j] > d[i][k] + d[k+1][j]) {
					d[i][j] = d[i][k] + d[k+1][j];
					dk[i][j] = k;
				}
		}
	myprint(1,n);
	cout << endl;
	return 0;
}
				
void myprint(int i,int j)
{
	if(i>j) return;
	if(i==j) {
		switch(a[i-1])
		{
			case '(':case ')':
				cout << "()";
				break;
			case '[':case']':
				cout << "[]";
				break;
			default:
				break;
		}
	} else {
		int k = dk[i][j];
		if(k == i-1) {
			cout << a[i-1];
			myprint(i+1,j-1);
			cout << a[j-1];
		} else{
			myprint(i,k);
			myprint(k+1,j);
		}
	}
			
}