Rain and Umbrellas

题意:某同学从x=0的点走到x=a的点,路上有几段路程是下雨的, 如果他需要经过这几段下雨的路程, 需要手上有伞, 每一把伞有一个重量, 求走到重点重量×路程的最小花费。

题解:暴力,如果某段路程需要带伞,就直接去找前面有伞的地点,如果不需要伞就直接往后走就好了。

代码:

 #include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int INF = 0x3f3f3f3f;
int rain[N];
int w[N];
int dp[N];
int main(){
int a, n, m, l, r;
scanf("%d%d%d", &a, &n, &m);
for(int i = ; i <= n; i++){
scanf("%d%d", &l, &r);
for(int j = l; j <= r; j++)
rain[j] = i;
}
memset(dp, INF, sizeof(dp));
memset(w, INF, sizeof(w));
for(int i = ; i <= m; i++){
scanf("%d%d", &l, &r);
w[l] = min(w[l], r);
}
dp[] = ;
for(int i = ; i < a; i++){
if(rain[i] == rain[i+] && rain[i]){
for(int j = ; j <= i; j++)
if(w[j]!=INF) dp[i+] = min(dp[i+], dp[j]+(i+-j)*w[j]);
}
else dp[i+] = dp[i];
}
printf("%d\n",dp[a]>=INF ? - : dp[a]); }

CF 988 F

最新文章

  1. MVC自定义分页(附表跳转页Loading提示)
  2. java.lang.Enum&lt;E extends Enum&lt;E&gt;&gt;
  3. [转]Getting Start With Node.JS Tools For Visual Studio
  4. 区分总结innerHeight与clientHeight、innerWidth与clientWidth、scrollLeft与pageXOffset等属性
  5. IOS的APNS和PushKit门道详述
  6. scala言语基础学习十
  7. codeforces 22E XOR on Segment 线段树
  8. 用VS2010开发Android应用的配置方法
  9. 3C Tic-tac-toe
  10. HDU 2435 There is a war (网络流-最小割)
  11. 使用Groovy进行依赖注入
  12. C语言库函数大全及应用实例十三
  13. 基于JDK1.8的ArrayList剖析
  14. 简单的ALV示例
  15. xml和java对象互转:JAXB注解的使用详解
  16. 迅雷磁力链接转BT种子工具
  17. js 使用a标签 下载资源
  18. 启用Flash Player 11.3的全屏键盘输入注意事项
  19. mssql sqlserver 保留小数位指定位数的2种方法分享
  20. 20155308《信息安全系统设计基础 嵌入式C语言课堂考试补博客

热门文章

  1. 【iOS】Masonry 自动布局 MASViewConstraint.m:207 错误
  2. 模拟器无Back、Menu等键
  3. 后端开发实践系列之二——领域驱动设计(DDD)编码实践
  4. Python之assert断言语句
  5. spring-boot项目的docker集成化部署(一)
  6. Android使用com.google.android.cameraview.CameraView进行拍照
  7. Layui多文件上传进度条
  8. java并发编程(二)----创建并运行java线程
  9. Linux--shell的基本特性--01
  10. 【KakaJSON手册】06_Model转JSON