codechef Chef and Bracket-Pairs
好dp啊，不会写，刚开始用分治写dfs不知道怎么样的数据错了，结果用的dpdp = dp + SUM(dp + dp) (a+a==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;
ll a;
int n;
int main(){
//freopen("a.txt","r",stdin);
//freopen(".out","w",stdout);
//dp表示上的正确式子的总数
//dp=1, dp=1
while(cin>>n)
{
rep(i,1,n)scanf("%lld", &a);
mset(dp);
rep(i,1,n){
dp=1;
dp=1;
}
for(int i=n-1; i>0; i--)
{
rep(j,i+1,n)
{
dp = dp;
rep(k, i+1, j)
{
if(a + a == 0 && a<0)
dp = (dp + dp*dp) % MOD;
}
//printf("dp[%d][%d]=%d\n", i, j, dp);
}
}
printf("%lld\n", dp%MOD);
}
return 0;
}
页:
[1]