首页 > 其他分享 >Polygon POJ - 1179

Polygon POJ - 1179

时间:2023-03-11 12:22:32浏览次数:48  
标签:Polygon int 1179 POJ include op

 

 

 除了维护一个区间最大值,还要一个最小值,( 有负数)

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std ;
 const int N=160;
 
 #define inf 1e9
 int n,a[N],f[N][N],g[N][N];
 char op[N] ;
 
 
 signed main(){
 	 int i,j,k;
 	 cin>>n;
 	 for(i=1;i<=n;i++){
 	 	cin>>op[i]>>a[i],a[i+n]=a[i],op[i+n]=op[i];
 	 }
 	 for(i=1;i<=n*2;i++)
 	  for(j=1;j<=n*2;j++) f[i][j]=-inf,g[i][j]=inf;
 	 for(i=1;i<=n*2;i++) f[i][i]=g[i][i]= a[i];
 	 
 	 for(int len=2;len<=n;len++)
 	  for(i=1;i+len-1<=2*n;i++){
 	  	j=i+len-1;
 	  	for(k=i;k<j;k++){
 	  		if(op[k+1]=='t'){
 	  			f[i][j]= max(f[i][j],f[i][k]+f[k+1][j]);
 	  			g[i][j]= min(g[i][j], g[i][k]+g[k+1][j]);
 	  		}
 	  		else{
 	  			f[i][j]=max(f[i][j],max(f[i][k]*f[k+1][j],
 	  			max(f[i][k]*g[k+1][j],max(g[i][k]*f[k+1][j],
 	  			g[i][k]*g[k+1][j]))));
 	  			
 	  			g[i][j]=min(g[i][j],min(f[i][k]*f[k+1][j],
 	  			min(f[i][k]*g[k+1][j],min(g[i][k]*f[k+1][j],
 	  			g[i][k]*g[k+1][j]))));
 	  		}
 	  	}
 	  }
 	  int ans= -inf;
 	  for(i=1;i<=n;i++)  ans=max(ans,f[i][i+n-1]);
 	  cout<<ans<<endl;
 	  for(i=1;i<=n;i++) if(f[i][i+n-1]==ans) cout<<i<<' ';
 }
 

 

标签:Polygon,int,1179,POJ,include,op
From: https://www.cnblogs.com/towboa/p/17205627.html

相关文章

  • Communication System POJ - 1018
    目前有一个公司需要购进宽带设备,每种设备有多款机器供选择,每种设备都需购进一台,现给出每台设备的带宽p与价格q,要求选择设备的最小带宽min(p)/add(q)(其中min(p)表示所有购......
  • OGRMultiPolygon使用范例
    最近在做OGRMultiPolygon相关开发的时候,遇到了新建OGRMultiPolygon对象无法正确释放的问题,后来找到示例代码,发现该对象不能直接new,以下为错误代码和正确代码的示例。/......
  • STL:map映照容器的简单用法(poj 2503 Babelfish)
    STL中map映照容器由一个键值和一个映照数据组成,具有一一对应的关系。结构为:键值--映照数据       例: aaa --111             bbb--222   ......
  • postgis之ST_MakePolygon
    ST_MakePolygon(geom1)geom1一个GEOMETRY数据类型的值,或一个计算结果为GEOMETRY类型的表达式。子类型必须是LINESTRING。linestring值必须是闭合的或为空。参考......
  • poj-1704 nim变形
    #include<stdio.h>#include<iostream>#include<math.h>#include<stdlib.h>#include<ctype.h>#include<algorithm>#include<vector>#include<string.h>#include<q......
  • poj-2348
    #include<stdio.h>#include<iostream>#include<math.h>#include<stdlib.h>#include<ctype.h>#include<algorithm>#include<vector>#include<string.h>#include<q......
  • poj-3669
    http://poj.org/problem?id=3669广搜#include<stdio.h>#include<iostream>#include<math.h>#include<stdlib.h>#include<ctype.h>#include<algorithm>#include......
  • js高德地图添加点Marker,添加线段Polyline,添加一个区域Polygon(面)
    高德地图JSAPI实例 亲测可用参考网站=>阿里云数据可视化平台(下载json用的):http://datav.aliyun.com/portal/school/atlas/area_selector?spm=a2crr.23498931.0.0.6859......
  • geotools存储带高程的Polygon(PolygonZM)
    geotools读取带高程的Polygon:geotools写入带高程的Polygon:>>Postgis如何读写带高程的多边形:https://www.cnblogs.com/2008nmj/p/17109774.html(MultiPolygonZ)   ST......
  • SPOJ Query On A Tree IV 题解
    SPOJQueryOnATreeIV题解一个边分治套线段树套堆的题目比较难写但是有不小的启发思路来源和代码都抄自[SPOJ-QTREE4]QUERYONATREEIV题解|KSKUN'sBlog简......