【BZOJ3156】防御准备(动态规划,斜率优化)
规划 优化 动态 准备 防御 斜率
2023-09-11 14:14:41 时间
【BZOJ3156】防御准备(动态规划,斜率优化)
题面
题解
从右往左好烦啊,直接\(reverse\)一下再看题。
设\(f[i]\)表示第\(i\)个位置强制建立检查站时,前面都满足条件的最小代价
\(f[i]=min(f[j]+sum[i-j-1])+A[i]\)
即枚举上一个检查站建立的位置。
假设存在\(k,j\)满足\(k<j\),并且\(j\)的转移优于\(k\)的转移。
那么\(f[j]+sum[i-j-1]<f[k]+sum[i-k-1]\)
因为\(sum\)这个和\(i,j,k\)有关,所以把它拆分一下,变成之与\(i\)以及只与\(j\)相关的式子
\(sum[i-j-1]=\sum_{k=1}^{i-j-1}k=sum[i-1]-sum[j]-(i-j-1)*j\)
然后再放回到上面的不等式。
即\(f[j]-sum[j]-(i-j-1)*j\lt f[k]-sum[k]-(i-k-1)*k\)
按照是否和\(i\)有关对于式子分类
\((f[j]-sum[j]+j^2+j)-(f[k]-sum[k]+k^2+k)\lt (j-k)*i\)
令\(g[i]=f[i]-sum[i]+i^2+i\)
直接除过去
\[i\gt \frac{g[j]-g[k]}{j-k}
\]
因为\(i\)单增,所以可以利用单调队列来完成斜率优化。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 1111111
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
ll f[MAX],s[MAX];
int n,a[MAX];
int Q[MAX],h,t;
double Slope(int i,int j){return ((f[i]-s[i]+1.0*i*i+i)-(f[j]-s[j]+1.0*j*j+j))/(i-j);}
int main()
{
n=read();
for(int i=1;i<=n;++i)a[i]=read();
reverse(&a[1],&a[n+1]);
for(int i=1;i<=n;++i)s[i]=s[i-1]+i;
/*
for(int i=2;i<=n;++i)
for(int j=1;j<i;++j)
f[i]=min(f[i],f[j]+s[i-1]-s[j]-j*(i-j-1)+a[i]);
*/
Q[h=t=1]=1;f[1]=a[1];
for(int i=2;i<=n;++i)
{
while(h<t&&Slope(Q[h],Q[h+1])<=i)++h;
int j=Q[h];f[i]=f[j]+s[i-1]-s[j]-j*(i-j-1)+a[i];
while(h<t&&Slope(Q[t],Q[t-1])>=Slope(Q[t-1],i))--t;
Q[++t]=i;
}
for(int i=1;i<=n;++i)f[n]=min(f[n],f[i]+s[n-i]);
printf("%lld\n",f[n]);
return 0;
}
相关文章
- Java动态规划实现最短路径问题
- 电子商务平台:云上高可用解决方案、优化、及未来规划
- 数学建模暑期集训15:matlab求解多目标规划模型
- Qt编写地图综合应用45-路径规划
- 62 leetcode 不同路径---动态规划
- Atitit 职位的规划与来源 1.1. 职位任命多元化1 1.2. 上级任命1 1.3. 自我推荐1 1.4. 他人推荐,1 1.5. 可以下级选举1 1.6. 缺席任命1 1.7.
- Atitit 我们的devops战略与规划 规范 推荐标准
- Atitit. Ati IDE 开发平台的第一版规划
- 【二阶锥规划】考虑气电联合需求响应的气电综合能源配网系统协调优化运行【IEEE33节点】(Matlab代码实现)
- 考虑交通网络流量的电动汽车充电站规划【IEEE33节点】(Matlab代码实现)
- 基于球向量的粒子群优化(SPSO)算法在无人机路径规划中的实现(Matlab代码实现)
- 【路径优化】基于改进的RRT算法的全局路径规划(Matlab代码实现)
- 【优化调度】基于改进遗传算法求解带时间窗约束多卫星任务规划(Matlab代码实现)
- 【无人机】四旋翼飞行器控制、路径规划和轨迹优化(Matlab代码实现)
- 基于智能优化算法的无人机路径规划(Matlab代码实现)
- 【优化模型】非线性规划问题
- 基于蚁群优化算法的三维路径规划算法matlab仿真
- 基于PSO粒子群优化算法的TSP路径规划matlab仿真
- m基于优化算法的多车辆的路径规划matlab仿真,对比GA,PSO以及烟花算法
- m基于自适应遗传优化的IEEE-6建设费用和网络损耗费用最小化电网规划算法matlab仿真
- 基于粒子群优化算法的移动机器人全局路径规划-附代码
- 790. 多米诺和托米诺平铺-动态规划算法优化
- [LeetCode] 62. 不同路径 ☆☆☆(动态规划)
- leetcode算法之动态规划总结(11种DP类型,70道全部搞懂)——总结非常全面
- Python小白的数学建模课-12.非线性规划
- 【软考】信息系统开发基础 - 信息系统规划(ISP)
- Kafka集群规划