首页 > 代码库 > [noip2005提高]过河 dp

[noip2005提高]过河 dp

2024-08-12 06:49:59   213人阅读

由于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,要特判，不能压缩；

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<algorithm> 6 #include<iomanip> 7 #include<cstdlib> 8 using namespace std; 9 const int maxn=110,maxm=20000;10 int L,S,T,M,N;11 int a[maxn];12 int vis[maxm],f[maxm];13 void init(){14     scanf("%d%d%d%d",&L,&S,&T,&M);15     for(int i=1;i<=M;i++)scanf("%d",&a[i]);16     sort(a+1,a+M+1);17 }18 void work(){19     int last=0;20     for(int i=1;i<=M;i++){21         if(a[i]-a[i-1]>100){vis[last+=100]=1;}22         else {vis[last+=a[i]-a[i-1]]=1;}23     }24     if(S==T){25         int sum=0;26         for(int i=1;i<=M;i++)if(a[i]%S==0)sum++;27         cout<<sum<<endl;28         return;29     }30     N=last;31     memset(f,127,sizeof(f));32     f[0]=0;33     for(int i=0;i<=N+10;i++){34         for(int j=S;j<=T;j++)f[i+j]=min(f[i+j],f[i]+vis[i+j]);35     }36     int minn=(1<<30);37     for(int i=N+1;i<=N+10;i++)minn=min(minn,f[i]);38     cout<<minn<<endl;39 }40 int main(){41     freopen("1.in","r",stdin);42     freopen("1.out","w",stdout);43     init();44     work();45 }
View Code

 

[noip2005提高]过河 dp


联系
我们