hdu5396Expression 区间dp

65 阅读 0 评论 43 点赞

我是靠谱客的博主仁爱橘子，最近开发中收集的这篇文章主要介绍hdu5396Expression 区间dp，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

//n(n<=200)个数字，n-1个运算符，运算符分别是"+,-,*"
//可以改变运算符大的运算顺序,那么有(n-1)!中运算结果
//问所有这些结果的和
//区间dp应该很好想到
//dp[i][j] 表示从i开始的j个数的(j-1)!中运算结果之和
//枚举最一个运算的运算符的位置
//那么对于'*'操作由于其分配率可以直接左右区间相乘就行
//对于'+'和'-'操作需要乘上另一个区间的情况的个数
//还有就是这些区间操作的顺序
//由于枚举了最后一个操作，左边区间和右边区间各自的顺序也确定
//但是左边和右边一起的顺序没有确定，这种情况的个数
//设左边区间x个操作符，右边y个
//那么情况个数就为c[x+y][x]个
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 110 ;
typedef long long ll  ;
const ll mod = 1e9+7 ;
ll dp[maxn][maxn] ;
ll c[maxn][maxn] ;
ll A[maxn] ;
char str[maxn] ;
void init()
{
    A[0] = 1 ;
    for(int i = 1;i < maxn;i++)
    A[i] = (A[i-1]*i)%mod ;
    for(int i = 0;i < maxn;i++)
    c[i][0] = c[i][i] = 1 ;
    for(int i = 1;i < maxn;i++)
      for(int j = 1;j < maxn;j++)
      c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod ;
}
int main()
{
    int  n ;
    init() ;
    while(~scanf("%d" , &n))
    {
        for(int i = 1;i <= n;i++)
        scanf("%lld" , &dp[i][1]) ;
        scanf("%s" , &str[1]) ;
        for(int j = 2;j <= n;j++)
          for(int i = 1;i <= n-j+1;i++)
          {
              dp[i][j] = 0 ;
              for(int k = 1;k < j;k++)
              {
                  ll tmp ;
                  if(str[i+k-1] == '+')
                  tmp = (dp[i][k]*A[j-k-1]+dp[i+k][j-k]*A[k-1])%mod ;
                  else if(str[i+k-1] == '-')
                  tmp = (dp[i][k]*A[j-k-1]-dp[i+k][j-k]*A[k-1])%mod ;
                  else if(str[i+k-1] == '*')
                  tmp = (dp[i][k]*dp[i+k][j-k])%mod ;
                  tmp = tmp*c[j-2][k-1]%mod ;
                  dp[i][j] =(dp[i][j] + tmp)%mod  ;
              }
          }
        printf("%lldn" , (dp[1][n]+mod)%mod) ;
    }
    return  0 ;
}