2015 Multi-University Training Contest 9 hdu 5396 Expression
Expression
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 175 Accepted Submission(s): 95
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\leq n \leq 100)$.
The second line contains n integers $a_1,a_2,⋯,a_n\quad(0≤a_i \leq 10^9)$.
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 $10^9+7$.
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn = 110; 5 const LL mod = 1000000007; 6 LL dp[maxn][maxn],c[maxn][maxn] = {1},f[maxn] = {1}; 7 void init() { 8 for(int i = 1; i < maxn; ++i) { 9 c[i][0] = c[i][i] = 1; 10 f[i] = f[i-1]*i%mod; 11 for(int j = 1; j < i; ++j) 12 c[i][j] = (c[i-1][j-1] + c[i-1][j])%mod; 13 } 14 } 15 char op[maxn]; 16 int main() { 17 init(); 18 int n; 19 while(~scanf("%d",&n)) { 20 memset(dp,0,sizeof dp); 21 for(int i = 0; i < n; ++i) 22 scanf("%I64d",&dp[i][i]); 23 scanf("%s",op); 24 for(int i = 2; i <= n; ++i) { 25 for(int j = 0; j + i <= n; ++j) { 26 for(int k = j,t = j + i -1; k < t; ++k) { 27 LL tmp; 28 if(op[k] == '+') 29 tmp = (f[t-k-1]*dp[j][k] + f[k-j]*dp[k+1][t])%mod; 30 else if(op[k] == '-') { 31 tmp = (f[t-k-1]*dp[j][k] - f[k-j]*dp[k+1][t])%mod; 32 tmp = (tmp + mod)%mod; 33 } else if(op[k] == '*') tmp = dp[j][k]*dp[k+1][t]%mod; 34 tmp = tmp*c[t-j-1][k-j]%mod; 35 dp[j][t] = (dp[j][t] + tmp + mod)%mod; 36 } 37 } 38 } 39 printf("%I64d\n",dp[0][n-1]); 40 } 41 return 0; 42 }
相关文章
- HDU 1013 Digital Roots
- HDU 1300 Pearls (DP)
- 【hdu 2594】Simpsons’ Hidden Talents
- 【hdu 3032】Nim or not Nim?
- 【hdu 3478】Catch
- HDU 1171 Big Event in HDU(01背包)
- HDU 4521 小明系列问题——小明序列 (线段树维护DP)
- HDU 2048 号码塔(DP)
- (hdu step 6.3.2)Girls and Boys(比赛离开后几个人求不匹配,与邻接矩阵)
- HDU 3081 Marriage Match II(二分法+最大流量)
- hdu 5040 BFS 多维化处理图
- HDU 3126 Nova [2009 Asia Wuhan Regional Contest Online]
- HDU 1325 Is It A Tree?