洛谷 P4342 [IOI1998]Polygon

题目传送门

解题思路:

一道环形dp,只不过有个地方要注意,因为有乘法,两个负数相乘是正数,所以最小的数是负数,乘起来可能比最大值大,所以要记录最小值(这道题是紫题的原因).

AC代码:

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 using namespace std;

 int n,a[],maxf[][],minf[][],ans = -;

 char c[];

 int main()

 {

     scanf("%d",&n);

     for(int i = ;i <= n; i++) {

         cin >> c[i] >> a[i];//char和string最好用cin,因为用了scanf调了好长时间

         a[i+n] = a[i];

         c[i+n] = c[i];

     }

     memset(minf,0x80,sizeof(minf));//最小值

     memset(maxf,0x3f,sizeof(maxf));//最大值

     for(int i = ;i <= n + n - ; i++) {

         maxf[i][i] = a[i];

         minf[i][i] = a[i];

     }

     for(int p = ;p <= n; p++)

         for(int i = ;i + p -  <= n + n - ; i++){

             int j = i + p - ;

             for(int k = i + ;k <= j; k++)

                 if(c[k] == 'x') {//如果是乘

                     minf[i][j] = max(minf[i][j],max(minf[i][k-] * minf[k][j],max(maxf[i][k-] * minf[k][j],max(minf[i][k-] * maxf[k][j],maxf[i][k-] * maxf[k][j]))));

                     maxf[i][j] = min(maxf[i][j],min(minf[i][k-] * minf[k][j],min(maxf[i][k-] * minf[k][j],min(minf[i][k-] * maxf[k][j],maxf[i][k-] * maxf[k][j]))));

                 }

                 else {

                     minf[i][j] = max(minf[i][j],minf[i][k-] + minf[k][j]);

                     maxf[i][j] = min(maxf[i][j],maxf[i][k-] + maxf[k][j]);

                 }

         }

     for(int i = ;i <= n; i++)

         ans = max(ans,minf[i][i+n-]);

     printf("%d\n",ans);

     for(int i = ;i <= n; i++)

         if(minf[i][i+n-] == ans)

             printf("%d ",i);

     return ;

 }