【BZOJ2037】Sue的小球(动态规划)
规划 动态 小球
2023-09-11 14:14:41 时间
【BZOJ2037】Sue的小球(动态规划)
题面
题解
莫名想到这道题目
很明显是一样的
设\(f[i][j][0/1]\)表示已经接到了\(i~j\)这一段的小球
当前在\(i\)或者在\(j\)的最小费用
这个费用是随着时间增长,没有被接到的小球产生的
这样就可以避免存下时间
提前就把费用减去
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
inline int read()
{
int x=0,t=1;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;
}
double f[1010][1010][2];
struct Ege{double x,y,v;}a[1010];
int n;
double S[1010];
double tot;
bool operator<(Ege a,Ege b){return a.x<b.x;}
int main()
{
n=read();double X=read();
for(int i=1;i<=n;++i)a[i].x=read();
for(int i=1;i<=n;++i)a[i].y=read();
for(int i=1;i<=n;++i)a[i].v=read();
sort(&a[1],&a[n+1]);
for(int i=1;i<=n;++i)S[i]=S[i-1]+a[i].v;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
f[i][j][0]=f[i][j][1]=1e18;
int l1=lower_bound(&a[1],&a[n+1],(Ege){X,0,0})-a;
f[l1][l1][0]=f[l1][l1][1]=1.0*abs(X-a[l1].x)*S[n];l1--;
f[l1][l1][0]=f[l1][l1][1]=1.0*abs(X-a[l1].x)*S[n];
for(int len=2;len<=n;++len)
for(int i=1;i<=n-len+1;i++)
{
int j=i+len-1;
f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+1.0*(a[i+1].x-a[i].x)*(S[i]+S[n]-S[j]));
f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+1.0*(a[j].x-a[i].x)*(S[i]+S[n]-S[j]));
f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+1.0*(a[j].x-a[i].x)*(S[i-1]+S[n]-S[j-1]));
f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+1.0*(a[j].x-a[j-1].x)*(S[i-1]+S[n]-S[j-1]));
}
for(int i=1;i<=n;++i)tot+=a[i].y;
printf("%.3lf\n",(tot-min(f[1][n][0],f[1][n][1]))/1000.00);
return 0;
}
相关文章
- 算法洗脑系列(8篇)——第七篇 动态规划
- Java实现 LeetCode 718 最长重复子数组(动态规划)
- 一些常见的递归算法 动态规划算法
- 动态规划专题
- 动态规划之最长公共子序列
- 数据结构和算法—动态规划
- 动态规划之背包问题
- 动态规划之最长公共子序列
- LeetCode-764. 最大加号标志【动态规划,二维数组】
- Leetcode学习计划之动态规划入门day12(118,119)
- Leetcode学习计划之动态规划入门day9(139,42)
- Atitit 院系和专业规划 大学里的院系,院一般指的都是学院,比如管理学院、法学院这种,系指的就是院里面的专业,比如中文系、哲学系这种。 中文系、哲学系 土木工程 目录 1. 经济管理学院2
- Atitit 我们的devops战略与规划 规范 推荐标准
- 【【henuacm2016级暑期训练】动态规划专题 H】Greenhouse Effect
- Algorithm之PrA:PrA之IP整数规划(包括0-1整数规划)算法经典案例剖析+Matlab编程实现
- 基于RRT算法的最优动力学路径规划(Matlab代码实现)
- 基于智能算法的无人机路径规划研究(Matlab代码实现)
- 【分布式能源的选址与定容】基于多目标粒子群算法分布式电源选址定容规划研究(Matlab代码实现)
- 多旋翼物流无人机节能轨迹规划(Python代码实现)
- 剑指 Offer 63. 股票的最大利润-动态规划算法
- 264. 丑数 II -动态规划算法
- 1906. 查询差绝对值的最小值-动态规划算法
- [LeetCode] 213. 打家劫舍II ☆☆☆(动态规划)
- Objective-C路成魔【2-Objective-C 规划】
- n每个计数的概率和发生骰子--动态规划
- 软件测试工程师是青春饭吗?--已过32的测试老鸟带你分析:软件测试职业发展规划
- 一文搞懂动态规划,上机考试再也不会慌