刷题总结——过河(NOIP2015)
题目:
题目背景
NOIP2005提高组试题2。
题目描述
在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为 0 的点表示桥的起点,坐标为 L 的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是 S 到 T 之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为 L 的点时,就算青蛙已经跳出了独木桥。
题目给出独木桥的长度 L,青蛙跳跃的距离范围 S,T ,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。
输入格式
输入文件的第一行有一个正整数 L(1 <= L <= 109),表示独木桥的长度。
第二行有三个正整数 S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中 1 <=S <= T <= 10,1 <= M <= 100。
第三行有 M 个不同的正整数分别表示这 M 个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。
所有相邻的整数之间用一个空格隔开。
输出格式
输出文件只包括一个整数,表示青蛙过河最少需要踩到的石子数。
样例数据 1
备注
【数据规模】
对于 30% 的数据,L <= 10000;
对于 100% 的数据,L <= 109。
题解:
引用ssoi官网题解:
状态:F[i] 跳到距离i处碰到的最少的石子数。
状态转移方程:F[i]=min{ F[i-k] } + F[i] (S<=k<=T i-k>=0)
边界条件:F[i]=1 i处有石子
目标结果:min{ F[k] } (L+1<=k<=L+T-1)
状态压缩:由于 L 最大为10^9,直接线性递推会超时。发现石子数很少,这意味着路径上有许多很长的空白段。我们可以把长度大于 ST 的空白段都缩小到 ST,这样最长只有 10090 了。
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int inf=1e9;
int l,s,t,m;
int pos[],rock[];
int dp[];
int main()
{
//freopen("a.in","r",stdin);
scanf("%d",&l);
scanf("%d%d%d",&s,&t,&m);
for(int i=;i<=m;i++)
scanf("%d",&pos[i]);
sort(pos+,pos+m+);
if(s==t)
{
int ans=;
for(int i=;i<=m;i++)
if(pos[i]%s==)
ans++;
cout<<ans<<endl;
}
else
{
int maxx=s*t;
for(int i=;i<=m;i++)
{
if(pos[i]-pos[i-]>maxx)
{
int temp=pos[i]-pos[i-]-maxx;
for(int j=i;j<=m;j++)
pos[j]-=temp;
}
}
l=pos[m]+;
for(int i=;i<=l-+t;i++)
dp[i]=inf;
dp[]=;
for(int i=;i<=m;i++)
rock[pos[i]]=;
for(int i=;i<=l-+t;i++)
{
for(int j=s;j<=t;j++)
{
if(i-j>=)
dp[i]=min(dp[i],dp[i-j]+rock[i]);
}
}
int ans=inf;
for(int i=l;i<=l-+t;i++)
ans=min(ans,dp[i]);
cout<<ans<<endl;
}
return ; }
最新文章
- 1125mysqbinlog日志
- http://www.cnblogs.com/softidea/p/5631763.html
- 锋利的jQuery-4--动画方法总结简表
- 尝试使用word发布博客
- 初试jQuery EasyUI
- [Swust OJ 409]--小鼠迷宫问题(BFS+记忆化搜索)
- PNG文件转png8
- 去掉 Warning:$HADOOP_HOME is deprecated
- HDU6038-Function-数学+思维-2017多校Team01
- Session 和 Cookie 区别
- python模块之xml
- vue项目编辑修改时批量回显数据
- luogu P3522 [POI2011]TEM-Temperature
- Spring Boot中CrudRepository与JpaRepository Dao中JpaRepository和JpaSpecificationExecutor查询
- 关于sklearn,监督学习几种模型的对比
- python加速包numba并行计算多线程
- linux及安全第五周总结——20135227黄晓妍
- I.MX6 CAAM
- JavaScript(核心、BOM、DOM)
- js怎样得出数组中某个数据最大连续出现的次数
热门文章
- IOS中Llabel整理
- 闹心的CSDN
- strophe.js 插件 XMPP openfire
- 洛谷 P1744 采购特价商品
- ios invalid put policy encoding 七牛上传报错
- Google Colab的一些注意事项
- WINDOWS-API:操作网络映射盘-WNetAddConnection2
- Codeforces Round #273 (Div. 2)-A. Initial Bet
- postman使用--构建工作流和newman
- BZOJ1009: [HNOI2008]GT考试 (矩阵快速幂 + DP)