HDOJ 1300 Pearls 斜率优化dp
2024-09-03 23:19:07
原题连接:http://acm.hdu.edu.cn/showproblem.php?pid=1300
题意:
题目太长了。。自己看吧
题解:
看懂题目,就会发现这是个傻逼dp题,斜率优化一下就好
代码:
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#define MAX_N 500
using namespace std; typedef long long ll; ll N;
ll sum[MAX_N]; ll dp[MAX_N];
ll a[MAX_N];
ll p[MAX_N]; double Y(int t){
return dp[t];
} double X(int t){
return sum[t];
} double Slope(int u,int v) {
return (Y(u) - Y(v)) / (X(u) - X(v));
} int que[MAX_N];
int T;
int main() {
cin.sync_with_stdio(false);
cin>>T;
while (T--) {
cin>>N;
memset(dp,,sizeof(dp));
memset(que,,sizeof(que));
memset(sum,,sizeof(sum));
for (int i = ; i <= N; i++) {
cin >> a[i] >> p[i];
sum[i] = sum[i - ] + a[i];
}
int front = , rear = ;
que[rear++] = ; for (int i = ; i <= N; i++) {
while (rear - front > && Slope(que[front], que[front + ]) <= p[i])front++;
int j = que[front];
dp[i] = dp[j] + (sum[i] - sum[j] + ) * p[i];
while (rear - front > && Slope(que[rear - ], que[rear - ]) >= Slope(que[rear - ], i))rear--;
que[rear++] = i;
}
cout << dp[N] << endl;
}
return ;
}
最新文章
- Shell脚本基础
- SEO:让搜索引擎对你的网站更有亲和力(译)
- Step by step SQL Server 2012的安装
- 【JAVA并发编程实战】7、日志服务
- View and Data API Tips: how to make viewer full screen
- struts2案例
- windows平台CodeBlocks MinGW C++11开发环境搭建
- C#中Brush、Color、String相互转换WPF/Silverlight
- cocos2dx 3.x(在Mac平台下利用Eclipse打包安卓apk安装包详细教程)
- windows7文件共享
- Easyui主从表设计
- Codeforces Round #338 (Div. 2) D. Multipliers 数论
- Spring 3.1 Environment Profiles--转载
- 给新手的 10 个有用 Linux 命令行技巧
- (原创)性能测试中,Oracle服务器定位CPU使用率高的瓶颈(SQL)
- select2 4.0.3 空记录时的处理
- 深入理解Spring Redis的使用 (八)、Spring Redis实现 注解 自动缓存
- AI tensorflow模型文件
- [math][mathematica] Mathematica进阶
- day39 css