题目大意:

...

Input

输入的第一行是单独一个整数n( 3 ≤ n ≤ 18 ),表示多边形的顶点数(同时也是边数)。

接下来第n行,每行包含一个运算符("+"或"*")和一个整数V[i]( -10 < V[i] < 10 ),分别表示第i条边所对应的运算符和第i个顶点上的数值。

Output

输出只有一个整数,表示最高得分W ( -231 < W < 231 )。

Sample Input

3
+ 2
* 3
+ 1

Sample Output

9

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
char e[];
ll d[],dp0[][],dp1[][];
/// 存在负数的情况 乘法时负负得正 所有要同时维护最大值和最小值
int main()
{
int n; scanf("%d\n",&n);
for(int i=;i<n;i++)
{
cin>>e[(i+n-)%n]>>d[i];
dp0[i][]=dp1[i][]=d[i];
}
/// 默认删除 选择的起点的前一条边
for(int r=;r<=n;r++)
for(int i=;i<n;i++)
{
dp0[i][r]=INF, dp1[i][r]=-INF;
for(int k=;k<r;k++)
{
ll a=dp0[i][k], b=dp0[(i+k)%n][r-k],
c=dp1[i][k], d=dp1[(i+k)%n][r-k];
/// 注意由于是环形 这两处必须取模
if(e[(i+k-)%n]=='*')
{
ll tmp[]={a*b,a*d,c*b,c*d};
sort(tmp,tmp+);
dp0[i][r]=min(dp0[i][r],tmp[]),
dp1[i][r]=max(dp1[i][r],tmp[]);
}
else
{
dp0[i][r]=min(dp0[i][r],a+b);
dp1[i][r]=max(dp1[i][r],c+d);
}
}
}
ll ans=;
for(int i=;i<n;i++)
ans=max(ans,dp1[i][n]);
printf("%lld\n",ans); return ;
}

最新文章

  1. ASP.NET MVC RenderPartial和Partial的区别
  2. Git版本控制管理学习笔记5-提交
  3. 《Pro Express.js》学习笔记——Express服务启动常规七步
  4. JVM基本结构
  5. 材价看板(1)- 如何建立你的第一个kanban,看看这些暴露的问题你们有没有?
  6. [IOS多线程]的使用:防止进行HTTP数据请求时,UI卡死。
  7. oracle 表空间使用情况
  8. mongodb配置及简单示例
  9. R语言将数据框转成xts
  10. iOS开发——网络编程Swift篇&amp;(四)异步Get方式
  11. Android 匿名共享内存C接口分析
  12. 移动前端meta
  13. java RTTI笔记 之Class学习笔记(摘自java编程思想)
  14. 深入学习CSS外边距margin(重叠效果,margin传递效果,margin:auto实现块级元素水平垂直居中效果)
  15. HBASE 基础命令总结
  16. MySQL主从同步问题
  17. 4步win7下简单FTP服务器搭建(试验成功)
  18. input type=&#39;number&#39;时,maxlength属性无效
  19. 【转载】C#调用C++ DLL
  20. 可视化的Redis数据库管理工具redis-desktop-manager的初步使用(图文详解)

热门文章

  1. NX二次开发-获取WCS标识UF_CSYS_ask_wcs
  2. OpenStack与KVM的区别与联系
  3. PaperWeekly 第五期------从Word2Vec到FastText
  4. Windows内存管理(1)--分配内核内存 和 使用链表
  5. Altium Designer 精心总结(转)
  6. LOJ #113. 最大异或和 (线性基)
  7. MySQL基础管理
  8. 当class有多个class属性时截取操作
  9. 16-Ubuntu-文件和目录命令-切换目录-cd
  10. js隐式类型转换,预编译、递归、作用域,作用域链、闭包、立即执行函数、继承圣杯模式