递推DP URAL 1031 Railway Tickets
2024-10-21 19:30:27
/*
简单递推DP:读题烦!在区间内的都更新一遍,dp[]初始化INF
注意:s1与s2大小不一定,坑!
详细解释:http://blog.csdn.net/kk303/article/details/6847948
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std; const int MAXN = 1e4 + ;
const int INF = 0x3f3f3f3f;
int C[], L[];
int dp[MAXN], a[MAXN]; int main(void) //URAL 1031 Railway Tickets
{
//freopen ("Y.in", "r", stdin); while (scanf ("%d%d%d%d%d%d", &L[], &L[], &L[], &C[], &C[], &C[]) == )
{
int n; scanf ("%d", &n);
int s1, s2;
scanf ("%d%d", &s1, &s2);
if (s1 > s2) swap (s1, s2);
a[] = ;
for (int i=; i<=n; ++i)
{
scanf ("%d", &a[i]); dp[i] = INF;
} dp[s1] = ;
for (int i=s1+; i<=s2; ++i)
{
for (int j=; j<=; ++j)
{
int k = i - ;
while (k >= s1)
{
if (a[i] - a[k] > L[j]) break;
if (dp[i] > dp[k] + C[j]) dp[i] = dp[k] + C[j];
k--;
}
}
} printf ("%d\n", dp[s2]);
} return ;
}
最新文章
- 代理IP收集
- CSS使用总结
- 如何进行服务器的批量管理以及python 的paramiko的模块
- 【Java学习笔记】数组使用
- 百度地图api之如何自定义标注图标
- SQL Server 死锁检查
- Oracle提示“资源正忙,需指定nowait”的解决方案
- js 下拉框效果
- HDU2579
- Centos下_MysqL5.7在使用mysqldump命令备份数据库报错:mysqldump: Got error: 1449: The user specified as a definer (&#39;fk_system&#39;@&#39;localhost&#39;) does not exist when using LOCK TABLES
- 【BZOJ4650】【NOI2016】优秀的拆分(后缀数组)
- maven下载及安装最详解
- fpc软排线焊接
- HDU 1086
- SQL语句利用日志写shell
- [git] 关闭 git branch 的pager
- NOIP2018 货币系统
- BI之报表测试总结
- 十、jdk工具之Jdb命令(The Java Debugger)
- 使用docker快速搭建环境-安装mysql
热门文章
- SpringMvc參数的接受以及serializeArray的使用方法
- 使用std::mutex取代QMutex
- hihoCoder 1584 Bounce 【数学规律】 (ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛)
- swing _JFileChooser文件选择窗口
- sjtu oj 1201. SuperXOR
- 汉字与区位码互转(天天使用Delphi的String存储的是内码,Windows记事本存储的文件也是内码),几个常见汉字的各种编码,utf8与unicode的编码在线查询,附有读书笔记 good
- sql索引原理以及优化
- glibc CVE-2015-7547漏洞的分析和修复方法【转】
- RegistryView
- 织梦文章分页后文章title的修改使得不一致