[noip2005提高]过河 dp

时间：2023-03-08 23:39:01
[noip2005提高]过河 dp

由于L的范围到了109，用普通dp做肯定是不成了；

可以观察到M的数量很小，dp在转移的过程中有大量的无用转移；

可以想到压缩范围，问题是如何压缩，观察若S=9，T=10时，能到达的点，9,10,18,19,20,27,28,29,30,36,37,38,39,40....80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120...

观察到了一定限度以后，可以跳到任意一个点；

所以可以根据这个压缩，压缩到100就可以了；

有一个地方需要注意，若S=T,要特判，不能压缩；

 #include<iostream>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<algorithm>

 #include<iomanip>

 #include<cstdlib>

 using namespace std;

 const int maxn=,maxm=;

 int L,S,T,M,N;

 int a[maxn];

 int vis[maxm],f[maxm];

 void init(){

     scanf("%d%d%d%d",&L,&S,&T,&M);

     for(int i=;i<=M;i++)scanf("%d",&a[i]);

     sort(a+,a+M+);

 }

 void work(){

     int last=;

     for(int i=;i<=M;i++){

         if(a[i]-a[i-]>){vis[last+=]=;}

         else {vis[last+=a[i]-a[i-]]=;}

     }

     if(S==T){

         int sum=;

         for(int i=;i<=M;i++)if(a[i]%S==)sum++;

         cout<<sum<<endl;

         return;

     }

     N=last;

     memset(f,,sizeof(f));

     f[]=;

     for(int i=;i<=N+;i++){

         for(int j=S;j<=T;j++)f[i+j]=min(f[i+j],f[i]+vis[i+j]);

     }

     int minn=(<<);

     for(int i=N+;i<=N+;i++)minn=min(minn,f[i]);

     cout<<minn<<endl;

 }

 int main(){

     freopen("1.in","r",stdin);

     freopen("1.out","w",stdout);

     init();

     work();

 }

相关文章