首页 > 代码库 > poj 1141 区间dp
poj 1141 区间dp
题目链接:http://poj.org/problem?id=1141
题解:略
代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define ll long long const int maxn=1e2+5; const int INF=0x3f3f3f3f; int dp[105][105]; int pos[105][105]; char str[105]; int Find(int x,int y) { if((str[x]==‘(‘ && str[y]==‘)‘) || (str[x]==‘[‘ && str[y]==‘]‘)) return 1; else return 0; } void print(int x,int y) { if(x>y) return; if(x==y) { if(str[x]==‘[‘ || str[x]==‘]‘) printf("[]"); else printf("()"); } else { if(pos[x][y]>=0) { print(x,pos[x][y]); print(pos[x][y]+1,y); } else if(str[x]==‘(‘) { printf("("); print(x+1,y-1); printf(")"); } else { printf("["); print(x+1,y-1); printf("]"); } } } int main() { //freopen("in.txt","r",stdin); scanf("%s",str+1); memset(pos,-1,sizeof(pos)); memset(dp,0,sizeof(dp)); int n=strlen(str+1); for(int i=1; i<=n; i++) dp[i][i]=1; for(int d=1; d<n; d++) { for(int i=1; i+d<=n; i++) { int j=i+d; dp[i][j]=INF; for(int 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]; pos[i][j]=k; } } if( Find(i,j) && dp[i+1][j-1]<dp[i][j] ) { dp[i][j]=dp[i+1][j-1]; pos[i][j]=-1; } } } print(1,n); puts(""); return 0; }
poj 1141 区间dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。