深信服笔试编程题第一题

题目：输入n个数字，n-1个符号，符号是加减乘除，在其中任意地方添加括号使结果最大

问一下各位大佬是不是区间dp，笔试时想当然的以为数字可以在任何地方，然后写了半天没写出来，最后十来分钟看题目没说数字可以随便顺序，然后想到了区间dp，花了一个小时写的，不知道是否正确

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define IN 10000000000

LL n;
LL a[10005];
char str[10005];
LL zd[1005][1005];
LL zx[1005][1005];



int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
cin>>str[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
zd[i][j]=-IN;
zx[i][j]=IN;
}
}
for(int i=1;i<=n;i++)
zd[i][i]=zx[i][i]=a[i];
for(int len=1;len<n;len++)
{
for(int i=1;i+len<=n;i++)
{
//cout<<1<<' '<<i<<endl;
if(str[i]=='*')
{
zd[i][i+len]=max(zd[i+1][i+len]*a[i],zd[i][i+len]);
zd[i][i+len]=max(zx[i+1][i+len]*a[i],zd[i][i+len]);
zx[i][i+len]=min(zd[i+1][i+len]*a[i],zx[i][i+len]);
zx[i][i+len]=min(zx[i+1][i+len]*a[i],zx[i][i+len]);
}
if(str[i]=='/')
{
zd[i][i+len]=max(a[i]/zd[i+1][i+len],zd[i][i+len]);
zd[i][i+len]=max(a[i]/zx[i+1][i+len],zd[i][i+len]);
zx[i][i+len]=min(a[i]/zd[i+1][i+len],zx[i][i+len]);
zx[i][i+len]=min(a[i]/zx[i+1][i+len],zx[i][i+len]);
}
if(str[i]=='+')
{
zd[i][i+len]=max(zd[i+1][i+len]+a[i],zd[i][i+len]);
zd[i][i+len]=max(zx[i+1][i+len]+a[i],zd[i][i+len]);
zx[i][i+len]=min(zd[i+1][i+len]+a[i],zx[i][i+len]);
zx[i][i+len]=min(zx[i+1][i+len]+a[i],zx[i][i+len]);
}
if(str[i]=='-')
{
zd[i][i+len]=max(a[i]-zd[i+1][i+len],zd[i][i+len]);
zd[i][i+len]=max(a[i]-zx[i+1][i+len],zd[i][i+len]);
zx[i][i+len]=min(a[i]-zd[i+1][i+len],zx[i][i+len]);
zx[i][i+len]=min(a[i]-zx[i+1][i+len],zx[i][i+len]);
}
if(str[i+len-1]=='*')
{
zd[i][i+len]=max(zd[i][i+len-1]*a[i+len],zd[i][i+len]);
zd[i][i+len]=max(zx[i][i+len-1]*a[i+len],zd[i][i+len]);
zx[i][i+len]=min(zd[i][i+len-1]*a[i+len],zx[i][i+len]);
zx[i][i+len]=min(zx[i][i+len-1]*a[i+len],zx[i][i+len]);
}
if(str[i+len-1]=='/')
{
zd[i][i+len]=max(zd[i][i+len-1]/a[i+len],zd[i][i+len]);
zd[i][i+len]=max(zx[i][i+len-1]/a[i+len],zd[i][i+len]);
zx[i][i+len]=min(zd[i][i+len-1]/a[i+len],zx[i][i+len]);
zx[i][i+len]=min(zx[i][i+len-1]/a[i+len],zx[i][i+len]);
}
if(str[i+len-1]=='+')
{
zd[i][i+len]=max(zd[i][i+len-1]+a[i+len],zd[i][i+len]);
zd[i][i+len]=max(zx[i][i+len-1]+a[i+len],zd[i][i+len]);
zx[i][i+len]=min(zd[i][i+len-1]+a[i+len],zx[i][i+len]);
zx[i][i+len]=min(zx[i][i+len-1]+a[i+len],zx[i][i+len]);
}
if(str[i+len-1]=='-')
{
zd[i][i+len]=max(zd[i][i+len-1]-a[i+len],zd[i][i+len]);
zd[i][i+len]=max(zx[i][i+len-1]-a[i+len],zd[i][i+len]);
zx[i][i+len]=min(zd[i][i+len-1]-a[i+len],zx[i][i+len]);
zx[i][i+len]=min(zx[i][i+len-1]-a[i+len],zx[i][i+len]);
}
//cout<<2<<endl;
for(int k=i+1;k+1<i+len;k++)
{
if(str[k]=='*')
{
zd[i][i+len]=max(zd[i+1][k]*zd[k+1][i+len],zd[i][i+len]);
zd[i][i+len]=max(zd[i+1][k]*zx[k+1][i+len],zd[i][i+len]);
zd[i][i+len]=max(zx[i+1][k]*zx[k+1][i+len],zd[i][i+len]);
zx[i][i+len]=min(zd[i+1][k]*zd[k+1][i+len],zx[i][i+len]);
zx[i][i+len]=min(zd[i+1][k]*zx[k+1][i+len],zx[i][i+len]);
zx[i][i+len]=min(zx[i+1][k]*zx[k+1][i+len],zx[i][i+len]);
}
if(str[k]=='/')
{
zd[i][i+len]=max(zd[i+1][k]/zd[k+1][i+len],zd[i][i+len]);
zd[i][i+len]=max(zd[i+1][k]/zx[k+1][i+len],zd[i][i+len]);
zd[i][i+len]=max(zx[i+1][k]/zx[k+1][i+len],zd[i][i+len]);
zx[i][i+len]=min(zd[i+1][k]/zd[k+1][i+len],zx[i][i+len]);
zx[i][i+len]=min(zd[i+1][k]/zx[k+1][i+len],zx[i][i+len]);
zx[i][i+len]=min(zx[i+1][k]/zx[k+1][i+len],zx[i][i+len]);
}
if(str[k]=='+')
{
zd[i][i+len]=max(zd[i+1][k]+zd[k+1][i+len],zd[i][i+len]);
zd[i][i+len]=max(zd[i+1][k]+zx[k+1][i+len],zd[i][i+len]);
zd[i][i+len]=max(zx[i+1][k]+zx[k+1][i+len],zd[i][i+len]);
zx[i][i+len]=min(zd[i+1][k]+zd[k+1][i+len],zx[i][i+len]);
zx[i][i+len]=min(zd[i+1][k]+zx[k+1][i+len],zx[i][i+len]);
zx[i][i+len]=min(zx[i+1][k]+zx[k+1][i+len],zx[i][i+len]);
}
if(str[k]=='-')
{
zd[i][i+len]=max(zd[i+1][k]-zd[k+1][i+len],zd[i][i+len]);
zd[i][i+len]=max(zd[i+1][k]-zx[k+1][i+len],zd[i][i+len]);
zd[i][i+len]=max(zx[i+1][k]-zx[k+1][i+len],zd[i][i+len]);
zx[i][i+len]=min(zd[i+1][k]-zd[k+1][i+len],zx[i][i+len]);
zx[i][i+len]=min(zd[i+1][k]-zx[k+1][i+len],zx[i][i+len]);
zx[i][i+len]=min(zx[i+1][k]-zx[k+1][i+len],zx[i][i+len]);
}
}
//cout<<zd[i][i+len]<<' '<<zx[i][i+len]<<"   ";
}
//cout<<endl;
}
cout<<zd[1][n]<<endl;
return 0;
}