Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
DP,洪水!#include <iostream> #include <stdio.h> #include <cstring> using namespace std; int main() { while(1){ char str[110]; scanf("%s", str); if(str[0] == 'e') return 0; int len = strlen(str); int res[110][110]; for(int i = 0; i <= len; i++){ res[i][i+1] = 0; res[i][i] = 0; } for(int cha = 2; cha <= len; cha++){ for(int i = 0; i <= len-cha; i++){ int j = i + cha; int m = 0; if((str[i] == '(' && str[j-1] == ')') || (str[i] == '[' && str[j-1] == ']')){ m = res[i+1][j-1] + 2; } for(int k = i+1; k < j; k++){ int temp = res[i][k] + res[k][j]; if(m < temp) m = temp; } res[i][j] = m; } } cout << res[0][len] << endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator