题目:http://poj.org/problem?id=1179

区间DP,值得注意的是有负值,而且有乘法,因此可能会影响最大值;

注意memset中写-1仅仅是-1,-2才是一个很小的负数;

最后找mxx时也要注意可能最大是负值,因此不能随便给mxx赋成0或-1之类。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,a[],mx[][],mn[][],ans[],t,INF=;
bool sid[][];
int main()
{
char dc;
scanf("%d ",&n);
memset(mx,-,sizeof mx);//-1仅是-1!
memset(mn,,sizeof mn);
for(int i=;i<=n;i++)
{
if(i==n)scanf("%c %d",&dc,&a[i]);
else scanf("%c %d ",&dc,&a[i]);
if(dc=='t')sid[i-][i]=;
else sid[i-][i]=;
a[i+n]=a[i];
sid[i-+n][i+n]=sid[i-][i];
mx[i][i]=a[i];mx[i+n][i+n]=a[i];
mn[i][i]=a[i];mn[i+n][i+n]=a[i];
}
for(int l=;l<=n;l++)
for(int i=;i<=n*-l;i++)//
{
int j=i+l-;
for(int k=i;k<j;k++)
{
if(sid[k][k+])
{
mx[i][j]=max(mx[i][j],mx[i][k]+mx[k+][j]);
mn[i][j]=min(mn[i][j],mn[i][k]+mn[k+][j]);
}
else
{
mx[i][j]=max(mx[i][j],mx[i][k]*mx[k+][j]);
mx[i][j]=max(mx[i][j],mn[i][k]*mn[k+][j]);
mx[i][j]=max(mx[i][j],mx[i][k]*mn[k+][j]);
mx[i][j]=max(mx[i][j],mn[i][k]*mx[k+][j]); mn[i][j]=min(mn[i][j],mx[i][k]*mx[k+][j]);
mn[i][j]=min(mn[i][j],mn[i][k]*mn[k+][j]);
mn[i][j]=min(mn[i][j],mx[i][k]*mn[k+][j]);
mn[i][j]=min(mn[i][j],mn[i][k]*mx[k+][j]);
}
}
}
int mxx=-INF;//!-1
// for(int i=1;i<=n;i++)
// {
// if(mx[i][i+n-1]>mxx)
// {
// memset(ans,0,sizeof ans);
// t=1;
// ans[t]=i;
// mxx=mx[i][i+n-1];
// }
// else if(mx[i][i+n-1]==mxx)ans[++t]=i;
// }
// printf("%d\n",mxx);
// for(int i=1;i<=t;i++)
// printf("%d ",ans[i]);
for(int i=;i<=n;i++)
mxx=max(mxx,mx[i][i+n-]);
printf("%d\n",mxx);
for(int i=;i<=n;i++)
if(mx[i][i+n-]==mxx)
printf("%d ",i);
return ;
}

最新文章

  1. 树莓派 Linux备忘
  2. 常用的web功能测试方法
  3. FTP上传-封装工具类
  4. NGUI 灰化按钮或图标
  5. Sprint(第五天11.18)
  6. [SoapUI] SoapUI JDBC REST 连接 Netezza
  7. nginx安装配置域名转发
  8. python 学习笔记 9 -- Python强大的自省简析
  9. Fragment里面嵌套Fragment的问题
  10. 两种方法实现asp.net方案的前后端数据交互(aspx文件、html+ashx+ajax)
  11. LAB1 partIV
  12. appserver WildFly 8.1 / jboss debug / jboss rmi
  13. 消息中间件——RabbitMQ
  14. mysql 查询优化~sql优化通用
  15. KafkaAPI实战
  16. [POI2015]LOG(树状数组)
  17. Linux 学习日记 1
  18. 页面跳转 Server.Transfer和 Response.Redirect的区别
  19. Oracle RAC Failover 详解
  20. MySQL集群Percona XtraDB Cluster安装搭建步骤详解

热门文章

  1. Android----SharedPreferences(存储数据)
  2. Uboot的串口下载文件命令:loads / loadb / loady
  3. Mysql 5.7.18 利用 MySQL proxies_priv(模拟角色)实现类似用户组管理
  4. KVM+VNC 虚拟机远程管理
  5. 【TensorFlow-windows】(七) CNN之VGG-net的测试
  6. 多媒体开发之---h264 NALU 语法结构
  7. The Gray World Assumption
  8. “volatile”这个关键字
  9. python 基础 4.5 用函数实现九九乘法表
  10. 如何学习CCIE