2015暑假多校联合---Expression(区间DP)
题目链接
http://acm.split.hdu.edu.cn/showproblem.php?pid=5396
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.
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.
Two numbers are considered different when they are in different positions.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#define eps 1e-8
#define maxn 105
#define inf 0x3f3f3f3f3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;
const long long mod=1e9+;
long long a[];
char s[];
long long dp[][];
long long A[];
long long C[][]; int main()
{
int n;
A[]=;
for(long long i=;i<=;i++) ///排列数;
A[i]=A[i-]*i%mod; for(int i=;i<;i++) ///组合数;
C[i][]=;
C[][]=;
for(int i=;i<;i++)
{
for(int j=;j<=i;j++)
C[i][j]=(C[i-][j-]+C[i-][j])%mod;
}
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=n;i++)
scanf("%lld",&a[i]);
scanf("%s",s+);
memset(dp,,sizeof(dp)); for(int i=;i<=n;i++)
dp[i][i]=a[i]; for(int len=;len<=n;len++)
{
for(int i=;i<=n;i++)
{
if(i+len->n) break;
for(int k=i;k<i+len-;k++)
{
long long t;
if(s[k]=='*')
t=(dp[i][k]*dp[k+][i+len-])%mod;
else if(s[k]=='-')
t=(dp[i][k]*A[i+len--k]-dp[k+][i+len-]*A[k-i])%mod;
else
t=(dp[i][k]*A[i+len--k]+dp[k+][i+len-]*A[k-i])%mod;
dp[i][i+len-]=(dp[i][i+len-]+t*C[len-][k-i])%mod;
}
}
}
printf("%lld\n",(dp[][n]%mod+mod)%mod);
}
return ;
}
最新文章
- laravel中TokenMismatchException异常处理
- Eclipse汉化后怎么改回英文版(可切换中英文)
- Unity3d 音效模块相关
- 异常:The absolute uri: http://www.springframework.org/security/tags cannot be resolved in either web.xml or the jar files deployed with this application
- Centos 如何安装Django环境
- typedef,static,const用法
- 华为机试 之 joseph环
- 使用JavaScript进行数组去重——一种高效的算法
- 超强、超详细Redis数据库入门教程(转载)
- 通过LRU实现通用高效的超时连接探测
- Python之在函数中使用列表作为默认参数
- C#-this关键字的功能之扩展方法
- Python isinstance 方法 判断 built-in types(内置类型)技巧
- go语言的安装与开发环境
- git 修改文件内容
- MYSQL + MHA +keepalive + VIP安装配置(二)--MHA的配置
- HADOOP与HDFS数据压缩格式
- mybatis的select、insert、update、delete语句
- APP 渠道推广【摘自网络】
- Java 为什么要使用反射(通俗易懂的举例)