多边形游戏 /// 区间DP oj1903
2024-10-07 22:16:33
题目大意:
...
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 ;
}
最新文章
- ASP.NET MVC RenderPartial和Partial的区别
- Git版本控制管理学习笔记5-提交
- 《Pro Express.js》学习笔记——Express服务启动常规七步
- JVM基本结构
- 材价看板(1)- 如何建立你的第一个kanban,看看这些暴露的问题你们有没有?
- [IOS多线程]的使用:防止进行HTTP数据请求时,UI卡死。
- oracle 表空间使用情况
- mongodb配置及简单示例
- R语言将数据框转成xts
- iOS开发——网络编程Swift篇&;(四)异步Get方式
- Android 匿名共享内存C接口分析
- 移动前端meta
- java RTTI笔记 之Class学习笔记(摘自java编程思想)
- 深入学习CSS外边距margin(重叠效果,margin传递效果,margin:auto实现块级元素水平垂直居中效果)
- HBASE 基础命令总结
- MySQL主从同步问题
- 4步win7下简单FTP服务器搭建(试验成功)
- input type=&#39;number&#39;时,maxlength属性无效
- 【转载】C#调用C++ DLL
- 可视化的Redis数据库管理工具redis-desktop-manager的初步使用(图文详解)
热门文章
- NX二次开发-获取WCS标识UF_CSYS_ask_wcs
- OpenStack与KVM的区别与联系
- PaperWeekly 第五期------从Word2Vec到FastText
- Windows内存管理(1)--分配内核内存 和 使用链表
- Altium Designer 精心总结(转)
- LOJ #113. 最大异或和 (线性基)
- MySQL基础管理
- 当class有多个class属性时截取操作
- 16-Ubuntu-文件和目录命令-切换目录-cd
- js隐式类型转换,预编译、递归、作用域,作用域链、闭包、立即执行函数、继承圣杯模式