1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| 这里写链接内容
错误程序
#include<cstdio>
#include<iostream>
using namespace std;
int n;
int a[9999];
int s[9999],f1[999][999];
int f2[999][999];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[n+i]=a[i];
s[i]=s[i-1]+a[i];
s[i+n]=s[i+n-1]+a[i];
}
// for(int i=1;i<=n;i++)
for(int i=1;i<=2*n;i++)
for(int j=1;j<=2*n;j++)
{
f1[i][j]=99999999;
f2[i][j]=-99999999;
}
for(int i=1;i<=2*n;i++)
{
f1[i][i]=0;
f2[i][i]=0;
}
for(int p=1;p<=n-1;p++)
for(int i=1;i<=2*n-p;i++)
{
int j=i+p;
for(int k=i;k<=j-1;k++)
{
f1[i][j]=min(f1[i][j],f1[i][k]+f1[k+1][j]+s[j]-s[i-1]);
f2[i][j]=max(f2[i][j],f2[i][k]+f2[k+1][j]+s[j]-s[i-1]);
}
}
int min1=99999999,max1=-99999999;
for(int i=1;i<=n;i++)
min1=min(f1[i][n+i-1],min1);
for(int i=1;i<=n;i++)
max1=max(f2[i][n+i-1],max1);
printf("%d\n%d",min1,max1);
return 0;
}
这个程序前缀和处理错了，在一开始还没处理好s[i]在s[n+i]里就调用了，以至于最小值求错了。
ac程序
#include<cstdio>
#include<iostream>
using namespace std;
int n;
int a[9999];
int s[9999],f1[999][999];
int f2[999][999];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[n+i]=a[i];
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++)
s[i+n]=s[i+n-1]+a[i];
for(int i=1;i<=2*n;i++)
for(int j=1;j<=2*n;j++)
{
f1[i][j]=99999999;
f2[i][j]=-99999999;
}
for(int i=1;i<=2*n;i++)
{
f1[i][i]=0;
f2[i][i]=0;
}
for(int p=1;p<=n-1;p++)
for(int i=1;i<=2*n-p;i++)
{
int j=i+p;
for(int k=i;k<=j-1;k++)
{
f1[i][j]=min(f1[i][j],f1[i][k]+f1[k+1][j]+s[j]-s[i-1]);
f2[i][j]=max(f2[i][j],f2[i][k]+f2[k+1][j]+s[j]-s[i-1]);
}
}
int min1=99999999,max1=-99999999;
for(int i=1;i<=n;i++)
min1=min(f1[i][n+i-1],min1);
for(int i=1;i<=n;i++)
max1=max(f2[i][n+i-1],max1);
printf("%d\n%d",min1,max1);
return 0;
}
只需要把前缀和弄到后面就ac了。。。
|
