HDU 5396 Expression 구간 DP

제목 설명:

Problem Description Teacher Mai has n numbers a1,a2,⋯,anand n−1 operators(“+”, “-” or “*”)op1,op2,⋯,opn−1, which are arranged in the form a1 op1 a2 op2 a3 ⋯ an.
He wants to erase numbers one by one. In i-th round, there are n+1−i numbers remained. He can erase two adjacent numbers and the operator between them, and then put a new number (derived from this one operation) in this position. After n−1 rounds, there is the only one number remained. The result of this sequence of operations is the last number remained.
He wants to know the sum of results of all different sequences of operations. Two sequences of operations are considered different if and only if in one round he chooses different numbers.
For example, a possible sequence of operations for “1+4∗6−8∗3” is 1+4∗6−8∗3→1+4∗(−2)∗3→1+(−8)∗3→(−7)∗3→−21.
Input There are multiple test cases.
For each test case, the first line contains one number n(2≤n≤100).
The second line contains n integers a1,a2,⋯,an(0≤ai≤109).
The third line contains a string with length n−1 consisting “+”,”-” and “*”, which represents the operator sequence.
Output For each test case print the answer modulo 109+7.
Sample Input

3
3 2 1
-+
5
1 4 6 8 3
+*-*

Sample Output

2
999999689

Hint Two numbers are considered different when they are in different positions.

제목 분석:

n개의 숫자를 입력하고 n-1개는'+'-'-'*'로 구성된 표현식입니다. 그 중에서 이 표현식의 연산 순서(우선순위가 다른 표현식에 괄호를 임의로 추가하는 것과 같음)를 임의로 바꾸고 모든 답안(연산 순서가 다른 것)을 합쳐서 1e9+7에 나머지를 줍니다.첫 번째 예제 3-2+1은 하나의 연산 순서일 뿐('+'와'-'연산 우선순위가 같기 때문에) 얻은 답은 2이다.두 번째 사례에서 얻은 답안은 사실 마이너스이고 1e9+7에 대한 모범을 취한 답안이 바로 이 값이다.dp[i][j]로 i개수에서 j개수 사이에서 나온 답안의 합을 나타낸다.i에서 j 사이의 k개 연산자를 처리합니다.만약'*'라면 좌우 양쪽 dp값을 곱한 후에 하나의 조합수를 곱하면 ij 사이의 j-i-1 연산자 중에서 k-i를 왼쪽으로 선택하고 나머지는 오른쪽의 조합수 C(j-i-1, k-i)를 선택한다.만약 '+' 또는 '-' 라면, 좌우 양쪽을 모두 배열된 개수에 곱해야 한다.마지막으로 답안을 처리하여 정수로 보증해야 한다.

코드는 다음과 같습니다.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>

typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 110;
const LL MOD = 1e9+7;
using namespace std;

LL dp[MAXN][MAXN];//dp[i][j]     (i,j)      
char op[MAXN];
LL S[MAXN];//    
LL C[MAXN][MAXN];//     


int n;
int main()
{
    S[0]=1;
    for(int i=1; i<=100; i++)
      S[i]=(S[i-1]*i)%MOD;
    C[0][0]=1;
    for(int i=1; i<=100; i++)
    {
        C[i][0]=1;
        for(int j=1; j<=100; j++)
        {
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;//     
        }
    }
    while(scanf("%d",&n)!=-1)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&dp[i][i]);
        }
        scanf("%s",op+1);
        for(int l=2; l<=n; l++)//    
        {
            for(int i=1; i+l-1<=n; i++)//    
            {
                int j=i+l-1;//  
                for(int k=i; k<j; k++)//   k    
                {
                    if (op[k]=='*') 
                       dp[i][j]+=(dp[i][k]*dp[k+1][j])%MOD*C[j-i-1][k-i]%MOD;
                    dp[i][j]%=MOD;
                    if (op[k]=='+') 
                       dp[i][j]+=(dp[i][k]*S[j-k-1]+dp[k+1][j]*S[k-i])%MOD*C[j-i-1][k-i]%MOD;
                    dp[i][j]%=MOD;
                    if (op[k]=='-') 
                       dp[i][j]+=(dp[i][k]*S[j-k-1]-dp[k+1][j]*S[k-i])%MOD*C[j-i-1][k-i]%MOD;
                    dp[i][j]%=MOD;
                }
            }
        }
        while(dp[1][n]<0) dp[1][n]+=MOD;
        printf("%lld
",dp[1][n]%MOD);
    }
    return 0;
}