太弱经常暴露智商.....

最近刷的个个dp都是区间，记忆化搜索也区间

然而窝组合数递推不会，规律推错了也不造，orz~~~

这题就找个规律，直接记忆化搜索干就是了，没什么难得

贴一发丑丑的代码，匿了

#include
     
      #include
      
       #include
       
        using namespace std;#define ll __int64const int mod=1e9+7;const int maxn=108;int a[maxn];char b[maxn];ll dp[maxn][maxn];ll pig[maxn][maxn],jie[maxn];void init(){    int i,j;    for(i=0;i<=100;i++)    {        pig[i][0]=pig[i][i]=1;        for(j=1;j
        
         =1&&r-i-1>=1)            {                 sum=(sum+pig[r-l-1][i-l]*(dp[l][i]*dp[i+1][r]%mod))%mod;            }            else                sum=(sum+dp[l][i]*dp[i+1][r])%mod;        }        if(b[i-1]=='-')        {            if(i-l>=1&&r-i-1>=1)            {                 sum=(sum+pig[r-l-1][i-l]*                ((jie[r-i-1]*dp[l][i]-jie[i-l]*dp[i+1][r])%mod))%mod;            }            else                sum=(sum+jie[r-i-1]*dp[l][i]-jie[i-l]*dp[i+1][r])%mod;        }        if(b[i-1]=='+')        {            if(i-l>=1&&r-i-1>=1)            {                 sum=(sum+pig[r-l-1][i-l]*                ((jie[r-i-1]*dp[l][i]+jie[i-l]*dp[i+1][r])%mod))%mod;            }            else            sum=(sum+jie[r-i-1]*dp[l][i]+jie[i-l]*dp[i+1][r])%mod;        }    }    dp[l][r]=sum;}int main(){    int i,j,n;    ll sum;    init();    initjie();    while(scanf("%d",&n)==1)    {        for(i=1;i<=n;i++)            scanf("%d",&a[i]);        scanf("%s",b);        memset(dp,-1,sizeof(dp));        dfs(1,n);        printf("%I64d\n",(dp[1][n]+mod)%mod);    }    return 0;}