【20181103T1】地球发动机【dp优化】
2024-10-19 06:20:24
一眼dp
设\(f_i\)表示前\(i\)个且\(i\)必须选的最大功率
有
\(f _i= max_{1 \leq j < i,A_i - A_j > X_j} \{f_j \}+p_i\)
下面的条件
\(A_i - A_j > X_j\)
相当于
\(X_j + A_j < A_i\)
\(X_j + A_j +1 \leq A_i\)
设\(g(i)= X_i +A_i +1\)
发现对于一个\(i\)来说\(g(i)\)是确定的
那我们可以用一个数据结构来维护
考场上用的树状数组，需要先预处理出\(g(i)\)然后离散化
复杂度\(O(NlogN)\)
和暴力\(N^2\)对了30min竟然没问题
造了个大数据发现输出INF……检查发现树状数组查询的返回值没开long long,好险啊
实际上不需要数据结构，只需要对于每台机器二分一下影响不到的最后的位置，然后倒着DP就可以了
最新文章
- Android中使用AsyncTask实现文件下载以及进度更新提示
- 转载文档：Storm实战常见问题及解决方案
- Android 媒体存储服务（二）
- Elasticsearch refresh vs. flush【转载】
- Android 开发之 Android 开发的起步
- 在matlab中执行dos环境中命令，并其读取结果画图
- c/c++ define用法
- 关于Visual Studio中的TraceDebugging文件夹
- Mac系统Git生成ssh公钥
- win8和ubuntu双系统
- 移动商城第四篇【Controller配置、添加品牌之文件上传和数据校验】
- [转载] epoll详解
- pyspider的一个诡异问题
- C# Invoke方法
- armv8 memory translation table descriptor
- SpringMvc使用FastJson做为json的转换器（注解方式）
- Java中goto和break、continue实现区别
- PAT甲题题解-1064. Complete Binary Search Tree (30)-中序和层次遍历，水
- Mongodb 与 SQL 语句对照表
- webform ajax 上传文件+参数