codechef Chef and Bracket-Pairs

战胜自己

　　好dp啊，不会写，刚开始用分治写dfs不知道怎么样的数据错了，结果用的dp
　　dp[j] = dp[i&#43;1][j] &#43; SUM(dp[i&#43;1][k] &#43; dp[k&#43;1][j]) (a&#43;a[k]==0 && a<0)
　　题目链接：http://www.codechef.com/problems/CHEFBR
　　

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
using namespace std;
#define INF 1e9
#define maxn 110
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define mset(x) memset(x,0,sizeof(x))
typedef long long ll;
const int MOD = 1e9+7;
ll dp[maxn][maxn];
ll a[maxn];
int n;
int main(){
//freopen(&quot;a.txt&quot;,&quot;r&quot;,stdin);
//freopen(&quot;.out&quot;,&quot;w&quot;,stdout);
//dp[j]表示[i, j]上的正确式子的总数
//dp=1, dp[i+1]=1
while(cin>>n)
{
rep(i,1,n)scanf(&quot;%lld&quot;, &a);
mset(dp);
rep(i,1,n){
dp=1;
dp[i+1]=1;
}
for(int i=n-1; i>0; i--)
{
rep(j,i+1,n)
{
dp[j] = dp[i+1][j];
rep(k, i+1, j)
{
if(a + a[k] == 0 && a<0)
dp[j] = (dp[j] + dp[i+1][k]*dp[k+1][j]) % MOD;
}
//printf(&quot;dp[%d][%d]=%d\n&quot;, i, j, dp[j]);
}
}
printf(&quot;%lld\n&quot;, dp[1][n]%MOD);
}
return 0;
}