如题：http://hihocoder.com/contest/challenge7/problem/1

题目1 : 正则表达式

dp的题目

dp[i][j]表示区间【i，j】是正则表达式

#include<iostream>@H_403_73@ using namespace std;@H_403_73@ #include<cstdio>@H_403_73@ #include<cstring>

@H_403_73@ char str[105];@H_403_73@ int dp[105][105];

@H_403_73@ int main()@H_403_73@ {@H_403_73@ //freopen("C:\\1.txt","r",stdin);@H_403_73@ while(~scanf("%s",str+1))@H_403_73@ {@H_403_73@ memset(dp,sizeof(dp));@H_403_73@ int i,j,k;@H_403_73@ int n=strlen(str+1);@H_403_73@ for(i=1;i<=n;i++)@H_403_73@ if(str[i]=='0'||str[i]=='1')@H_403_73@ dp[i][i]=1;

for(i=2;i<=n;i++)@H_403_73@ for(j=1;j+i-1<=n;j++)@H_403_73@ {@H_403_73@ for(k=j;k<j+i-1&&!dp[j][i+j-1];k++)@H_403_73@ if(dp[j][k]&&dp[k+1][i+j-1])@H_403_73@ dp[j][i+j-1]=1;@H_403_73@ for(k=j+1;k<j+i-1&&!dp[j][i+j-1];k++)@H_403_73@ if(str[k]=='|'&&dp[j][k-1]&&dp[k+1][i+j-1])@H_403_73@ dp[j][i+j-1]=1;@H_403_73@ if(str[j+i-1]=='*'&&dp[j][j+i-2])@H_403_73@ dp[j][j+i-1]=1;@H_403_73@ if(str[j]=='('&&str[i+j-1]==')'&&dp[j+1][i+j-2])@H_403_73@ dp[j][j+i-1]=1;

} if(dp[1][n]) printf("yes\n"); else printf("no\n"); } return 0; }