# 47 条题解

• @ 2019-03-13 20:29:33

被两点坑了
1.最大=最大*最大or最小*最小；最小=最大*最大or最大*最小or最小*最大or最大*最小
2.初始化不能是0。

``````#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const long long inf = 0x7fffffffffffffff;
char c[110];
int vis[110][110][2],n;  //3-d 0小 1大
long long d[110][110][2],smax,smin=inf;
long long dp(int i,int j,int f){ //左闭右开
long long &ans = d[i][j][f];
if(vis[i][j][f]) return ans;
vis[i][j][f] = 1;
if(i+1==j) return ans;
for(int k=i+1;k<j;k++){
if(f) ans = max(ans,c[k-1]=='*'?max(dp(i,k,1)*dp(k,j,1),dp(i,k,0)*dp(k,j,0)):dp(i,k,1)+dp(k,j,1));
else ans = min(ans,c[k-1]=='*'?min(min(dp(i,k,0)*dp(k,j,0),dp(i,k,1)*dp(k,j,1)),min(dp(i,k,1)*dp(k,j,0),dp(i,k,0)*dp(k,j,1))):dp(i,k,f)+dp(k,j,f));
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;i++){
cin>>c[i];
c[n+i] = c[i];
}
for(int i=0;i<2*n;i++) for(int j=0;j<2*n;j++) d[i][j][0] = inf,d[i][j][1]=-inf;
for(int i=0;i<n;i++){
cin>>d[i][i+1][0];
d[i+n][i+n+1][1] = d[i+n][i+n+1][0] = d[i][i+1][1] = d[i][i+1][0];
}
for(int i=0;i<n;i++){
smax = max(smax,dp(i,i+n,1));
smin = min(smin,dp(i,i+n,0));
}
cout<<smax<<'\n'<<smin;
return 0;
}

``````
• @ 2017-08-22 00:13:29

由于乘法的特殊性，状态转移需分5种情况，然后是简单的区间dp了

代码如下

``````#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int n,dp[104][104][2],maxx=-0x3f3f3f3f,minn=0x3f3f3f3f;//0---max,1---min
string s;
int work(int a,int b,char ch){
if(ch=='+') return a+b;
else return a*b;
}
int main(){
scanf("%d",&n);
string s;
cin>>s;
s=s+s;
for(int i=1;i<2*n;i++)
for(int j=1;j<2*n;j++){
dp[i][j][1]=0x3f3f3f3f;
dp[i][j][0]=-0x3f3f3f3f;
}
for(int i=1;i<=n;i++){
scanf("%d",&dp[i][i][0]);
dp[n+i][n+i][1]=dp[n+i][n+i][0]=dp[i][i][1]=dp[i][i][0];
}
for(int l=1;l<=n;l++){
for(int i=1;i<=2*n-1;i++){
int j=i+l-1;
if(j>=2*n) break;
for(int k=i;k<j;k++){
dp[i][j][0]=max(dp[i][j][0],work(dp[i][k][0],dp[k+1][j][0],s[k-1]));
dp[i][j][0]=max(dp[i][j][0],work(dp[i][k][1],dp[k+1][j][1],s[k-1]));
dp[i][j][1]=min(dp[i][j][1],work(dp[i][k][1],dp[k+1][j][1],s[k-1]));
dp[i][j][1]=min(dp[i][j][1],work(dp[i][k][0],dp[k+1][j][1],s[k-1]));
dp[i][j][1]=min(dp[i][j][1],work(dp[i][k][1],dp[k+1][j][0],s[k-1]));
}
}
}
for(int i=1;i<=n;i++){
maxx=max(maxx,dp[i][i+n-1][0]);
minn=min(minn,dp[i][i+n-1][1]);
}
printf("%d\n%d",maxx,minn);
}
``````
• @ 2017-02-26 19:58:10

总算AC了其实并不难= =

• @ 2016-08-02 21:48:37

强烈BS此题，有负数的情况！

• @ 2016-05-22 11:04:21
1. 破环成链
2. 注意初始化：不能赋0
3. 注意数据范围：longint，保险开int64
4. 注意**负数**
1. 最大值可以由*最大x最大*和*最小x最小*（负负得正）两种情况得到
2. 最小值可以由*最小x最小*和*最大x最小*（正负得负）得到
``````uses math;
const inf=99999999999;
var
n,
amax,amin,
i,j,k,l:longint; //[i,j],j-i+1=l,k in [i,j]
e:array[0..100] of char;
v:array[0..100] of int64;
dmax,dmin:array[0..100,0..100] of int64;

function union(a,b:longint;c:char):longint;
begin
case c of
'*':union:=a*b;
'+':union:=a+b;
end;
end;

begin
for i:=1 to n do begin
e[i+n]:=e[i];
end;
for i:=1 to n do begin
v[i+n]:=v[i];
end;
fillqword(dmax,sizeof(dmax) div 8,-inf);
fillqword(dmin,sizeof(dmin) div 8,inf);
for i:=1 to 2*n do begin
dmax[i,i]:=v[i];
dmin[i,i]:=v[i];
end;

for l:=2 to 2*n do begin
for i:=1 to 2*n+1-l do begin
j:=i+l-1;
for k:=i to j-1 do begin
dmin[i,j]:=min(min(dmin[i,j],
union(dmax[i,k],dmin[k+1,j],e[k])),
min(union(dmin[i,k],dmax[k+1,j],e[k]),
union(dmin[i,k],dmin[k+1,j],e[k]))
);
dmax[i,j]:=max(dmax[i,j],
max(union(dmax[i,k],dmax[k+1,j],e[k]),
union(dmin[i,k],dmin[k+1,j],e[k]))
);
end;
end;
end;

amax:=-inf;amin:=inf;
for i:=1 to n do begin
amax:=max(amax,dmax[i,i+n-1]);
amin:=min(amin,dmin[i,i+n-1]);
end;
writeln(amax);writeln(amin);
end.
``````
• @ 2015-09-28 20:28:35

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int n;
int fmin0[105][105], fmax0[105][105];
char prtr[105];
bool vis[105][105], vis1[105][105];

int calcu(int x0, int x1, char c)
{
if (c == '*')
return x0 * x1;
else
return x0 + x1;
}
int max0(int x0, int x1, int x2, int x3, int x4)
{
return max(x4, max(x0, max(x1, max(x2, x3))));
}
int min0(int x0, int x1, int x2, int x3, int x4)
{
return min(x4, min(x0, min(x1, min(x2, x3))));
}
int main(int argc, const char *argv[])
{
scanf("%d", &n);
scanf("%s", prtr);
for (int i = 1; i <= n * 2; ++i)
for (int j = 1; j <= n * 2; ++j)
{
fmin0[i][j] = 2147483647;
fmax0[i][j] = -2147483647;
}
for (int i = 1; i <= n; ++i)
{
scanf("%d", &fmin0[i][i]);
fmin0[i + n][i + n] = fmax0[i + n][i + n] = fmax0[i][i] = fmin0[i][i];
}
for (int i = n; i >= 1; --i)
prtr[i] = prtr[i - 1];
for (int i = n + 1; i <= n * 2; ++i)
prtr[i] = prtr[i - n];
for (int p = 1; p <= n - 1; ++p)
for (int i = 1; i <= n * 2 - p; ++i)
for (int j = i + 1; j <= i + p; ++j)
{
if (vis[i][j])
continue;
vis[i][j] = true;
for (int k = i; k < j; ++k)
{
fmax0[i][j] = max0(
fmax0[i][j],
calcu(fmax0[i][k], fmax0[k + 1][j], prtr[k]),
calcu(fmax0[i][k], fmin0[k + 1][j], prtr[k]),
calcu(fmin0[i][k], fmin0[k + 1][j], prtr[k]),
calcu(fmin0[i][k], fmax0[k + 1][j], prtr[k])
);
fmin0[i][j] = min0(
fmin0[i][j],
calcu(fmax0[i][k], fmax0[k + 1][j], prtr[k]),
calcu(fmax0[i][k], fmin0[k + 1][j], prtr[k]),
calcu(fmin0[i][k], fmin0[k + 1][j], prtr[k]),
calcu(fmin0[i][k], fmax0[k + 1][j], prtr[k])
);
}
}
int ans1, ans2;
ans1 = -2147483647;
ans2 = 2147483647;
for (int i = 1; i <= n; ++i)
{
ans1 = max(ans1, fmax0[i][i + n - 1]);
ans2 = min(ans2, fmin0[i][i + n - 1]);
}
printf("%d\n%d\n", ans1, ans2);
return 0;
}

• @ 2015-01-11 22:34:43

发个清晰一点的代码。虽然比较长，但应该还好理解。说明几点：
1. dbNum=2*num-1，用于把数据展开（如1 1 3 4展开为1 1 3 4 1 1 3）从而规避复杂的取余处理
2. 状态转移时，要区分加和乘。乘法会有5种情况
3. 函数MAX和MIN有5个参数，当比较的变量数小于5时，使用极值填充来避免干扰

#include <stdio.h>
#include <limits.h>
char operators[105];
int operands[105];
int maxArr[105][105],minArr[105][105];
int MAX(int a,int b,int c,int d,int e){
a=a>b?a:b;
a=a>c?a:c;
a=a>d?a:d;
return a>e?a:e;
}
int MIN(int a,int b,int c,int d,int e){
a=a<b?a:b;
a=a<c?a:c;
a=a<d?a:d;
return a<e?a:e;
}
int main(){
int num,dbNum;
int i,begin,end,mid;
scanf("%d",&num);
scanf("%s",operators);
for(i=0;i<num;i++)
scanf("%d",&operands[i]);
dbNum=num*2-1;
for(i=num;i<dbNum;i++){
operators[i]=operators[i-num];
operands[i]=operands[i-num];
}
for(begin=0;begin<dbNum;begin++){
for(end=0;end<dbNum;end++){
maxArr[begin][end]=LONG_MIN;
minArr[begin][end]=LONG_MAX;
}
}
for(i=0;i<dbNum;i++)
maxArr[i][i]=minArr[i][i]=operands[i];
for(i=1;i<num;i++){
for(begin=0;begin<dbNum;begin++){
end=begin+i;
if(end>dbNum)
break;
for(mid=begin;mid<end;mid++){
if(operators[mid]=='+'){
maxArr[begin][end]=MAX(
maxArr[begin][end],
maxArr[begin][mid]+maxArr[mid+1][end],
LONG_MIN,LONG_MIN,LONG_MIN
);
minArr[begin][end]=MIN(
minArr[begin][end],
minArr[begin][mid]+minArr[mid+1][end],
LONG_MAX,LONG_MAX,LONG_MAX
);
}else if(operators[mid]=='*'){
maxArr[begin][end]=MAX(
maxArr[begin][end],
maxArr[begin][mid]*maxArr[mid+1][end],
maxArr[begin][mid]*minArr[mid+1][end],
minArr[begin][mid]*maxArr[mid+1][end],
minArr[begin][mid]*minArr[mid+1][end]
);
minArr[begin][end]=MIN(
minArr[begin][end],
maxArr[begin][mid]*maxArr[mid+1][end],
maxArr[begin][mid]*minArr[mid+1][end],
minArr[begin][mid]*maxArr[mid+1][end],
minArr[begin][mid]*minArr[mid+1][end]
);
}
}
}
}
int n=LONG_MIN,m=LONG_MAX;
for(begin=0;begin<num;begin++){
if(n<maxArr[begin][begin+num-1])
n=maxArr[begin][begin+num-1];
if(m>minArr[begin][begin+num-1])
m=minArr[begin][begin+num-1];
}
printf("%d\n%d\n",n,m);
return 0;
}

• @ 2014-08-15 08:40:07

*program P1565;
*var
* minopt,maxopt:array[0..200,0..200] of longint;
* ch:array[1..200] of char;
* point:array[1..200] of longint;
* n,i,k,l,j,mi,ma:longint;
*function min(x,y:longint):longint;
* begin
* if x>y then exit(y);
* exit(x);
* end;
*function max(x,y:longint):longint;
* begin
* max:=x;
* if x<y then max:=y;
* end;
*begin
* for i:=1 to n do
* begin
* ch[i+n]:=ch[i];
* end;
* for i:=1 to n do
* begin
* point[i+n]:=point[i];
* minopt[i,i]:=point[i];
*minopt[i+n,i+n]:=point[i];
* maxopt[i,i]:=point[i];
* maxopt[i+n,i+n]:=point[i];
*end;
* for i:=1 to 2*n do
* for j:=1 to 2*n do
* if i<>j then
* begin
* maxopt[i,j]:=-maxlongint;
* minopt[i,j]:=maxlongint;
* end;
* for l:=1 to n-1 do
* for i:=1 to 2*n-1-l do
* begin
* for k:=i to i+l-1 do
* begin
* if ch[k]='+' then
* begin
* maxopt[i,i+l]:=max(maxopt[i,i+l],maxopt[i,k]+maxopt[k+1,i+l]);
* minopt[i,i+l]:=min(minopt[i,i+l],minopt[i,k]+minopt[k+1,i+l]);
* end;
* if ch[k]='*' then
* begin
* maxopt[i,i+l]:=max(maxopt[i,i+l],maxopt[i,k]*maxopt[k+1,i+l]);
* minopt[i,i+l]:=min(minopt[i,i+l],minopt[i,k]*minopt[k+1,i+l]);
* maxopt[i,i+l]:=max(maxopt[i,i+l],minopt[i,k]*minopt[k+1,i+l]);
* minopt[i,i+l]:=min(minopt[i,i+l],maxopt[i,k]*maxopt[k+1,i+l]);
* maxopt[i,i+l]:=max(maxopt[i,i+l],minopt[i,k]*maxopt[k+1,i+l]);
* minopt[i,i+l]:=min(minopt[i,i+l],maxopt[i,k]*minopt[k+1,i+l]);
* maxopt[i,i+l]:=max(maxopt[i,i+l],maxopt[i,k]*minopt[k+1,i+l]);
* minopt[i,i+l]:=min(minopt[i,i+l],minopt[i,k]*maxopt[k+1,i+l]);
* end;
* end;
* end;
*mi:=maxlongint;
* ma:=-maxlongint;
* for i:=1 to n do
* begin
* if mi>minopt[i,i+n-1] then mi:=minopt[i,i+n-1];
* if ma<maxopt[i,i+n-1] then ma:=maxopt[i,i+n-1];
* end;
* writeln(ma);
* writeln(mi);
*end.

• @ 2014-08-07 09:01:30

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const long long maxe=1000000000;
#define ll long long
ll minn,maxn,save[1000],f[200][200][2];
ll Min(ll a,ll b,ll c,ll d)
{
ll tmp=maxe;
tmp=min(tmp,a);
tmp=min(tmp,b);
tmp=min(tmp,c);
tmp=min(tmp,d);
return tmp;
}
ll Max(ll a,ll b,ll c,ll d)
{
ll tmp=-maxe;
tmp=max(tmp,a);
tmp=max(tmp,b);
tmp=max(tmp,c);
tmp=max(tmp,d);
return tmp;
}
char st[200];
int n,op[200];
void dfs(int l,int r)
{
ll num=maxe;
ll ans=-maxe;
if(f[l][r][0]==-maxe)
{
if(l==r)
{
f[l][r][0]=save[l];
}
else
{
for(int i=l;i<r;i++)
{
dfs(l,i);
dfs(i+1,r);
if(op[i]==1)
{
num=f[l][i][0]+f[i+1][r][0];
}
if(op[i]==2)
{
num=Max(f[l][i][0]*f[i+1][r][0],f[l][i][1]*f[i+1][r][0],f[l][i][0]*f[i+1][r][1],f[l][i][1]*f[i+1][r][1]);
}
if (num>ans)
ans=num;
}
f[l][r][0]=ans;
}
}
ans=maxe;
if(f[l][r][1]==maxe)
{
if(l==r)
{
f[l][r][1]=save[l];
}
else
{
for(int i=l;i<r;i++)
{
dfs(l,i);
dfs(i+1,r);
if(op[i]==1)
{
num=f[l][i][1]+f[i+1][r][1];
}
if(op[i]==2)
{
num=Min(f[l][i][0]*f[i+1][r][0],f[l][i][1]*f[i+1][r][0],f[l][i][0]*f[i+1][r][1],f[l][i][1]*f[i+1][r][1]);
}
if (num<ans)
ans=num;
}
f[l][r][1]=ans;
}
}
}
int main()
{
minn=maxe;
maxn=-maxe;
scanf("%d",&n);
scanf("%s",st+1);
for(int i=1;i<=2*n;i++)
{
for(int j=1;j<=2*n;j++)
{
f[i][j][1]=maxe;
f[i][j][0]=-maxe;
}
}
for(int i=1;i<=n;i++)
{
if(st[i]=='+')
op[i]=1;
if(st[i]=='*')
op[i]=2;
scanf("%lld",&save[i]);
}
for(int i=n+1;i<=2*n;i++)
{
op[i]=op[i-n];
save[i]=save[i-n];
}
ll ans1=minn;
ll ans2=maxn;
for(int i=1;i<=n;i++)
{
dfs(i,i+n-1);
maxn=max(maxn,f[i][i+n-1][0]);
minn=min(minn,f[i][i+n-1][1]);
}
printf("%lld\n%lld",maxn,minn);
return 0;
}

• @ 2014-08-07 09:01:23

测试数据 #0: Accepted, time = 0 ms, mem = 876 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 880 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 876 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 880 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 876 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 876 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 876 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 876 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 880 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 880 KiB, score = 10
Accepted, time = 30 ms, mem = 880 KiB, score = 100

• @ 2009-10-06 20:40:34

可恶！！！！辛辛苦苦写的高精居然不用。。。。。。而且题目没说明有负数！也没说数的大小范围！！！！

简直就是个三无题目！！！！BS!!!!!!!!坑人啊！！！

• @ 2009-10-06 07:33:18

数组初值不要设成0，要设成max或min

• @ 2009-09-05 22:28:04

有点像石子合并的DP

• @ 2009-08-26 12:46:33

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

真不容易，提交了这么多次，首先要注意负数乘法的问题，如果只有第九个点不过，就象我很多次没过，就是max[]数组初值的问题

memset(max,-1,sizeof(max));

memset(min,1,sizeof(min));

就可以了，感谢wjh……

• @ 2009-08-06 09:48:04

奇怪！怎么没说顶点值的范围，longint够了吗？要开long long吗？要上高精度吗？出题真不严谨！！

• @ 2009-08-03 14:17:45

const Max_size=10000000;

var work:array[0..100] of boolean;

fmax,fmin:array[0..100,0..100] of longint;

a:array[0..100] of longint;

n,m,i,k,j,l,p,maxans,minans:longint;

ch:char;

function max(a,b,c,d,e:longint):longint;

begin

max:=a;

if maxe then min:=e;

end;

begin

for i:=1 to n do

begin

end;

for i:=1 to n do read(a[i]);

m:=n*2-1;

for i:=n+1 to m do

begin

work[i]:=work; a[i]:=a;

end;

fillchar(fmax,sizeof(fmax),200);

fillchar(fmin,sizeof(fmin),100);

for i:=1 to m do

begin

fmax:=a[i]; fmin:=a[i];

end;

for i:=1 to n-1 do

for k:=1 to m do

begin

j:=i+k; if j>m then break;

for p:=k to j-1 do

if work[p] then

begin

fmax[k,j]:=max(fmax[k,j],fmax[k,p]+fmax[p+1,j],-Max_size,-Max_size,-Max_size);

fmin[k,j]:=min(fmin[k,j],fmin[k,p]+fmin[p+1,j],Max_size,Max_size,Max_size);

end else

begin

fmax[k,j]:=max(fmax[k,j],fmin[k,p]*fmin[p+1,j],fmax[k,p]*fmax[p+1,j],fmax[k,p]*fmin[p+1,j],fmin[k,p]*fmax[p+1,j]);

fmin[k,j]:=min(fmin[k,j],fmin[k,p]*fmin[p+1,j],fmax[k,p]*fmax[p+1,j],fmax[k,p]*fmin[p+1,j],fmin[k,p]*fmax[p+1,j]);

end;

end;

maxans:=-Max_size; minans:=Max_size;

for i:=1 to n do

begin

if fmax>maxans then maxans:=fmax;

if fmin

• @ 2009-08-01 19:30:22

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：34ms

终于过了，好BT啊

• @ 2009-07-25 11:12:49

搞了N久,比大小比错了,晕死,AC率又降了,哎,细节啊!!!!我是第111个AC的!

庆祝第200题!!!

Flag 　　Accepted

题号 　　P1565

类型(?) 　　动态规划

通过 　　111人

提交 　　553次

通过率 　　20%

难度 　　1

• @ 2009-07-25 11:09:55

.............

• @ 2009-07-16 19:13:20

zgx我恨你。。。。

ID
1565

7

1707

320

19%

4