考察:区间DP
思路:
f[i][j]表示[i,j]区间的最大得分,那么状态转移方程f[l][r] = max(f[l][r],calc(f[l][k],f[k+1][r],op[k+1])
calc函数是什么呢,根据定义f[i][j]表示i,j区间合并后的最大得分,calc就是再将f[l][k]与f[k+1][r]合并,op[k+1]就是边的符号.信心满满的交上去后,可以过四个点
那么哪里出了问题呢?注意到数字有负数,并且存在乘法,因此最大值可能是两个负数最小值相乘,也可能是正数最大值相加(乘).因此这道题要计算最大值,还需要记录区间计算的最小值.注意最小值是由两区间最大值或最小值转移而来.
最后枚举断点,当前断点就是第一步要断的边.
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 const int N = 110,M =2;
6 int nums[N],n,f[N][N],ans;
7 bool op[N];//1表示+ 0表示*
8 char s[M];
9 int calc(int a,int b,int x)
10 {
11 if(x) return a+b;
12 else return a*b;
13 }
14 void solve()
15 {
16 for(int i=1;i<=2*n;i++) f[i][i] = nums[i];
17 for(int len=2;len<=n*2;len++)
18 for(int l=1;l+len-1<=2*n;l++)
19 {
20 int r = l+len-1;
21 for(int k=l;k<r;k++)
22 f[l][r] = max(calc(f[l][k],f[k+1][r],op[k+1]),f[l][r]);
23 }
24 }
25 int main()
26 {
27 scanf("%d",&n);
28 for(int i=1;i<=n;i++)
29 {
30 scanf("%s%d",s,&nums[i]);
31 if(s[0]=='t') op[i] = 1;
32 else op[i] = 0;
33 nums[i+n] = nums[i];
34 op[i+n] = op[i];
35 }
36 memset(f,-0x3f,sizeof f);
37 ans = -0x3f3f3f3f;
38 solve();
39 for(int i=1;i<=n;i++) ans = max(ans,f[i][i+n-1]);
40 printf("%d\n",ans);
41 for(int i=1;i<=n;i++)
42 if(f[i][i+n-1]==ans)
43 printf("%d ",i);
44 return 0;
45 }