47 条题解
-
1
^ambition LV 8 @ 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; } -
0
由于乘法的特殊性，状态转移需分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); } -
0
- 破环成链
- 注意初始化：不能赋0
- 注意数据范围：longint，保险开int64
- 注意**负数**
- 最大值可以由*最大x最大*和*最小x最小*（负负得正）两种情况得到
- 最小值可以由*最小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 readln(n); for i:=1 to n do begin read(e[i]); e[i+n]:=e[i]; end; for i:=1 to n do begin read(v[i]); 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. -
0
feng_lingsong LV 9 @ 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;
} -
0
wang_yanheng LV 10 @ 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;
} -
0
*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
* readln(n);
* for i:=1 to n do
* begin
* read(ch[i]);
* ch[i+n]:=ch[i];
* end;
* for i:=1 to n do
* begin
* read(point[i]);
* 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. -
0
#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;
} -
0
测试数据 #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 -
0
zhangyuchi45 LV 8 @ 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…… -
0
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
readln(n);
for i:=1 to n do
begin
read(ch); work[i]:=ch='+';
end;
readln;
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 -
0
zhanghanyuan LV 10 @ 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啊 -
0
w122185976 LV 10 @ 2009-07-25 11:12:49
搞了N久,比大小比错了,晕死,AC率又降了,哎,细节啊!!!!我是第111个AC的!
庆祝第200题!!!
Flag Accepted
题号 P1565
类型(?) 动态规划
通过 111人
提交 553次
通过率 20%
难度 1 -
0
.............
^ambition
LV 8
@ 2019-03-13 20:29:33
