当前位置: 首页 > news >正文

题解:P5504 [JSOI2011] 柠檬

题目:

下面给个经典的 DP 式子不多说了:

\[f_i=f_j+s_iqz^2(s_i,i)+s_iqz^2(s_{j+1},j)-2s_iqz(s_i,i)qz(s_{j+1},j),s_{j+1}=s_i \]

单调栈太阴了!下面有个 hack:

11
2 10 2 2 10 2 2 10 2 2 2
ans:128

众所周知 \(x,k\) 都单调的题我们可以用单调队列维护。
但是这题是上凸包且 \(k\) 递增,手画一下,我们会发现我们实际上决策点是从右端点开始缩。总的看下来是个单调栈。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int QAQ=1e5+7,ovo=1e4+7;
int n,s[QAQ];
vector<int> qz[ovo];
int qzh(int s,int i) {return upper_bound(qz[s].begin(),qz[s].end(),i)-qz[s].begin();}
struct dian {int x,y;} ;
vector<dian> zhan[ovo];
const double inf=1e18;
double xie(dian a,dian b)
{if(a.x==b.x) return (b.y>=a.y)?inf:-inf;return (1.0*b.y-1.0*a.y)/(1.0*b.x-1.0*a.x);
}
int l[ovo],r[QAQ],f[QAQ],ans;
signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>s[i],qz[s[i]].push_back(i);for(int i=1;i<=10000;i++) zhan[i].push_back({0,0});for(int i=1;i<=n;i++){ int ccx=qzh(s[i],i);int k=2*s[i]*ccx;while(l[s[i]]<r[s[i]]&&xie(zhan[s[i]][r[s[i]]-1],zhan[s[i]][r[s[i]]])<=k)r[s[i]]--;f[i]=s[i]*ccx*ccx+zhan[s[i]][r[s[i]]].y-k*zhan[s[i]][r[s[i]]].x;int swl=qzh(s[i+1],i);dian nw={swl,f[i]+s[i+1]*swl*swl};while(l[s[i+1]]<r[s[i+1]]&&xie(zhan[s[i+1]][r[s[i+1]]-1],zhan[s[i+1]][r[s[i+1]]])<=xie(zhan[s[i+1]][r[s[i+1]]-1],nw))r[s[i+1]]--;++r[s[i+1]];if(zhan[s[i+1]].size()<=r[s[i+1]]) zhan[s[i+1]].push_back(nw);else zhan[s[i+1]][r[s[i+1]]]=nw;ans=max(ans,f[i]);}cout<<ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=24264

相关文章:

  • Thymeleaf教程
  • Vmware虚拟机设置中处理器数量和内核内存再次探讨
  • VMware中Ubuntu迁移(复制)后进入紧急模式You are in emergency mode.
  • 太简单了!原来PS在线抠图可以这么玩,背景分离无压力
  • 深入解析:【Leetcode】随笔
  • 实用指南:Linux驱动之V4L2
  • 儿童与青少年数据安全及体育发展新方向会议
  • 威联通NAS Emby-Server 的SQLite数据库损坏和程序损坏修复
  • Embarcadero Dev-C++ 6.3 中文乱码问题 - 教程
  • 2025.10.4——2绿
  • 十月四日就听《10월 4일》
  • windows上的实用小软件
  • 比赛题2
  • ZR 2025 十一集训 Day 4
  • 价值处理单元(VPU)专题研究:从价值危机到透明决策的计算革命——声明Ai研究
  • 13-Neo4j Desktop
  • 中兴ZXHN F450光猫关闭TR069实录
  • 完整教程:六款智能证照工具盘点,打造个性化“数字身份档案”
  • 随机化学习笔记
  • PWN手的从成长之路-08-not_the_same_3dsctf_2016-溢出+函数调用劫持
  • 12-windows11的WSL详解
  • 完整教程:如何将文件从电脑传输到安卓设备
  • [vmware+openeuler22.03]创建软RAID
  • C++右值引用
  • 价值处理单元(VPU)专题研究:构建可信AI的基石
  • NOIP模拟赛记录
  • 软件工程第一次作业--关于未来规划和自我发展
  • 2025太阳能厂家推荐天津龙腾,太阳能热水系统,发电系统,光伏热系统,热水工程系统,预加热系统,中央热水系统,彩图发电系统,分户储水系统,分户计量系统推荐
  • 集训模拟赛日志
  • 1688 商品采集 API 调用全流程分享:从准备到实操 - 实践