题目描述 Description
某登上景点处有个N级台阶,一个人想从台阶底部登到顶部。一些台阶上长有青苔,此人要尽可能少地走到有青苔的台阶上。可用一维整数坐标:0,1,…,N(其中N是台阶级数)表示各级台阶的位置。坐标为0的点表示台阶底部,N表示终点。此人从台阶的底部,走向台阶的顶部(只能上不能下),一步可跨越的台阶数是D到E之间的任意正整数(包括D,E)。当人的坐标大于等于N时,就算登顶。
如果给出了台阶的级数N,此人走一步可跨过台阶的级数D,E,青苔所在的位置(正整数),那么从台阶底部登到顶部至少要踩到多少级有青苔的台阶?
输入描述 Input Description
第一行有1个正整数N,表示台阶的级数。(1≤N≤1,000,000,000)
第二行有3个正整数D,E,F,用空格隔开,分别表示人一步可跨过的最小和最大台阶数,以及长有青苔的台阶数。其中1≤D≤E≤10,1≤F≤100。
第三行开始,有F个不同的正整数,分别表示有青苔的台阶的坐标(台阶底部和顶部没有青苔)。这些整数用空格隔开。
输出描述 Output Description
一个整数,表示登顶最少需要踩到长有青苔的台阶的级数。
样例输入 Sample Input
10 1 2 4 2 3 5 7
样例输出 Sample Output
1
奉上80分RE代码:
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<sstream>
#include<stack>
#include<fstream>
#include<list>
using namespace std;
long long f[10000005]={};
long long g[105]={};
long long n,a,b,m,ans=0x3f3f3f3f;
long long search(long long x){
int l=0,r=m-1;
while(l<r){
int mid=(l+r)>>1;
if(g[mid]<x){
l=mid+1;
}else if(g[mid]==x){
return 1;
}else{
r=mid;
}
}
return 0;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>a>>b>>m;
for(long long i=0;i<m;i++){
cin>>g[i];
}
sort(g,g+m);
f[0]=search(0);
for(long long i=1;i<=n-1+b;i++){
f[i]=0x3f3f3f3f;
for(long long j=a;j<=min(b,i);j++){
f[i]=min(f[i],f[i-j])+search(i);
}
}
for(long long i=n;i<=n-1+b;i++){
ans=min(ans,f[i]);
}
cout<<ans;
//fclose(stdin);
//fclose(stdout);
return 0;
}
这个递推状态转移方程简单而且和酷丁猫爬楼梯一样,我就想知道再怎么优化数组大小(N≤1,000,000,000这怎么定义数组)
本来数组模拟的台阶状态已经改成了二分,我真的想不到其他的办法了
测试点#10(只能看一眼哦~)
输入(显示前50行):
351550744 7 7 56 12112390 19934755 21236277 26192930 36484235 39421956 41774517 43715264 51566957 51587765 57722353 69357892 73313721 84733915 86545669 89533864 99808617 117814956 129776834 132686837 136999968 143654558 143814092 146118338 147807921 148246738 150795471 175255063 177852567 179515137 185046013 188319695 189769711 191832938 202038063 204340047 214687832 215141061 215609087 220461156 228258586 230630902 234311804 244497450 258141185 260218034 265843390 275474120 275476564 282237454 283311082 307631581 308566864 315989447 324637820 346431394
输出(显示前50行):
6