poly.cpp

来自「内有5个常用算法」· C++ 代码 · 共 79 行

#include <stdio.h>
#include <ctype.h>
#define max 50

int minf,maxf,m[max][max][2];
char op[max];
int n;

void MinMax(int i,int j,int k)
{
    int e[4], s, 
        a=m[i][k][0], 
        b=m[i][k][1],
        r=(i+k+1)%n,
        c=m[r][j-k-1][0],
        d=m[r][j-k-1][1];
    if (op[(r-1+n)%n]=='t') 
	{
        minf=a+c;
        maxf=b+d;
    } 
	else 
	{
        e[0]=a*c;
        e[1]=a*d;
        e[2]=b*c;
        e[3]=b*d;
        minf=e[0];
        maxf=e[0];
        for(s=1;s<4;s++) 
		{
            if(minf>e[s])minf=e[s];
            if(maxf<e[s])maxf=e[s];
        }
    }
}


int PolyMax()
{
    int i,j,k,temp;
    for(j=1;j<n;j ++)
        for(i=0; i<n; i++)
            for(k=0;k<j;k++) 
			{
                MinMax(i,j,k);
                if(m[i][j][0]>minf)
					m[i][j][0]=minf;
                if(m[i][j][1]<maxf)
					m[i][j][1]=maxf;
            }
    temp=m[0][n-1][1];
    for (i=1;i<n;i++)
        if(temp<m[i][n-1][1])temp=m[i][n-1][1];

	return temp;
   
}


void main()
{
    int i;
    char ch;
	scanf("%d",&n);
    for(i=0;i<n;i++) 
	{ 
        while((ch=getchar())&& isspace(ch));
		if(i==0)
			op[n-1]=ch;
		else
			op[i-1]=ch;
		scanf("%d", &m[i][0][0]);
        m[i][0][1]=m[i][0][0];
    }
    int value=PolyMax();
	printf("最大值为：%d\n",value);
}