关键词：
https://www.vijos.org/p/1002
分析：很容易想到f[i]=min(f[i],f[i-j]+is_stone[i])的递推式，但L高达10^9，很明显会TLE，我们发现m<= 100，在长达1到10^9的线段里就只有100个点这是多么的稀疏，我们看看有什么方法压缩一下，引用：
问题的关键就是多么长的空地才能保证青蛙对这些空地是处处可达的？假设这个距离是X，
那么比X长的空地也都是处处可达的，就与长为X的空地等效了，因此这就是压缩长度的关键。
最后的结论是X=T^2。青蛙跳跃X需要跳T次T长度，但是可以把每个T逐个换成S（也就是T-1）
那么TS到TT就是跳T次能到达的所有格子了。而跳T-1次能到达的最大长度为(T-1)T=ST，
与跳T次的最小长度衔接上了。而T的最大值是10，也就是X取100。
因此先对输入数据进行一次初始化，如果发现两个石子之间的长度比100大，那么就直接视为它们相距100即可。
a[i]=a[i-1]+(a[i]-a[i-1])%90;即可压缩
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxm=110,mod=100,maxn=100010,inf=999999999; int L,s,t,m,a[maxm],f[maxn]; bool book[maxn]; int main(){ cin>>L>>s>>t>>m; for(int i=1;i<=m;++i)cin>>a[i]; sort(a+1,a+1+m); if(s==t){ int ans=0; for(int i=1;i<=m;++i){ if(a[i]%s==0)++ans; } cout<<ans; return 0; } //压缩 for(int i=1;i<=m;++i){ int dis=a[i]-a[i-1]; a[i]=dis%mod+a[i-1]; } L=a[m]; for(int i=1;i<=m;++i){ book[a[i]]=1; } f[0]=0; for(int i=1;i<=L+t;++i){ f[i]=inf; for(int j=s;j<=t;++j){ if(i-j<0)break; f[i]=min(f[i],f[i-j]+book[i]); } } int ans=inf; for(int i=L;i<=L+t;++i){ ans=min(ans,f[i]); } cout<<ans; return 0; }
p1002过河卒
题面题面看题面第一眼就觉得是DFS看了一下提示，结果很大=v=,想了一下用递推==就是类似于小学奥数首先是输入先把地图上马能踩到的位置标出来 查看详情
vijos1002
假设两块石头之间最多能跳了x次t。最少跳s*x，最多跳t*x。如果t*x-s*x>=9，一定可以跳到下一块石头前t块中的任意一块。注意要排除掉s=t的情况，不然会T两个点。#include<cstdio>#include<cctype>#include<algorithm>usingnamespacest... 查看详情
p1002过河卒(代码片段)
此题用滚动数组即可#include<cstdio>#include<cstring>usingnamespacestd;typedefunsignedlonglongull;ullf[50][50];inta[12]=0,-1,-2,-2,-1,1,2,2,1,0;intb[12]=0,2,1,-1,-2,-2,-1,1,2,0;inttx,ty;inthx,hy; 查看详情
洛谷p1002过河卒
...了。感受到了时代的进步呢。题目描述棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之... 查看详情
luogu_1002过河卒
//哇塞，真的坑，要longlong== #include<iostream>usingnamespacestd;longlonga[30][30];intn,m,x,y,sum;boolb[30][30];voidC(intx,inty){ b[x][y]=b[x+1][y+2]=b[x+2][y+1]=true; if(x>=1)b[x-1][y+2]=true 查看详情
luogup1002过河卒
题目描述棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋... 查看详情
ac日记——过河卒洛谷1002
题目描述棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋... 查看详情
p1002[noip2002普及组]过河卒变种的走方格问题(代码片段)
https://www.luogu.com.cn/problem/P1002如果没有马的限制那么就是一个很经典的求走方格的路径问题。但是加了马的限制，只需初始化是稍加变种即可。#include<bits/stdc++.h>usingnamespacestd;constintN=55;longlongintf[N][N];intn,m,x,y;voi 查看详情
vijos在vijos的自己的域中创建题目(代码片段)
创建属于自己的域https://vijos.org/填入对应信息即可。创建题目点击题库往下拉，点击创建题目进入题目之后，点击设置接下来就是重点，配置数据点：（如果想直接用，后面有捷径。）写一个正确答案... 查看详情
vijos1057盖房子
二次联通门: Vijos1057盖房子 /*Vijos1057盖房子简单的dp当前点(i,j)所能构成的最大的正方形的边长为点(i-1,j-1)与(i,j-1),(i-1,j)三点中最小的边长构成..一遍递推,一边取最大即可*/#include<cstdio>#defineMax1009inlineintmin(inta,intb){... 查看详情
[noip2002]过河卒
[NOIP2002]普及组]过河卒小结定义两个long型数组，代表棋盘和存放 查看详情
vijos1412多人背包
01背包+归并看的题解 https://vijos.org/p/1412/solution#include<cstdio>#include<cstring>usingnamespacestd;inta[205];intb[205];intf[5005][55];intk,n,v;voidwork(int*aa,int*bb,intc){intt[105];intt 查看详情
老农过河
java老农过河问题解决http://www.52pojie.cn/thread-550328-1-1.html http://bbs.itheima.com/thread-141470-1-1.htmlhttp://touch-2011.iteye.com/blog/1104628 查看详情
过河卒（bfs）(代码片段)
过河卒TimeLimit:5000MSMemoryLimit:65536KTotalSubmit:296(91users)TotalAccepted:73(56users)Rating:SpecialJudge:NoDescriptionLda学会了中国象棋，在一次与Kevin的切磋中，Lda不幸只剩下一只过河卒了，而Kevin还有很多棋子。过河卒在棋盘上 查看详情
vijos1285&1283&1282&1284佳佳的魔法药水/魔杖/魔法照片/魔法阵
题目链接：https://vijos.org/p/1285https://vijos.org/p/1283https://vijos.org/p/1282https://vijos.org/p/1284 查看详情
算法编程过河问题
今天偶尔想到了过河问题。记得读小学六年级的时候第一次接触到这个问题--六个老虎过河问题(百度上有具体介绍，本文解决的是一个简单的问题。下一篇文章中将讨论该问题)，当时都是从逻辑思维的方法得到正确的... 查看详情
vijos1982子串
感谢http://blog.csdn.net/gengmingrui/article/details/49849023#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#definemaxn1050#definemaxm250#definemod10000000 查看详情
poj1700
...来的）当总人数大于等于4时，有两种情况1最快和最慢的过河，最快的回来； 最快和次慢的过河，最快的回来。2最快和次快的过河，最快的回来； 最慢和次慢的过河，次快的回来。每次反复迭代，直到总人数比四小。若总人... 查看详情