Vijos 1002 過河，vijos1002過河

Vijos 1002 過河，vijos1002過河

     這是我寫的在Vijos上的第一題。這道題在我剛學完DP的時候，就做過。當時年少輕狂，沒有看數據的范圍，直接暴力DP，結果TLE。。。。後來就沒有再碰過。知道最近覺得快要省賽了，有必要把原來沒有做出來的題做一做，於是有了這篇博客。

    從那時學完的最簡單的動規後，又學了一個名叫狀壓DP的算法，狀壓即狀態壓縮，把沒有用的狀態全部排除掉。BZOJ上就有一道狀壓DP的題(互不侵犯king)傳送門！！而過河這道題就是一道狀壓DP。根據我現在的習慣，做題先看數據范圍，然後判定算法。（1 <= L <= 10^9）這麼大的數，根據經驗應該用log級的算法，但是再看題目顯然用不到任何log級的算法。而應該是DP。那麼既然是DP又有這麼大的數據范圍，所以應該是狀壓DP。這樣算法就判斷出來了。那麼該怎麼壓縮呢？這裡要用到一個定理

Px+(P+1)y=Q     

      x,y是未知數，P是跳躍的距離，P+1也是跳躍的距離，對於任意Q，Q>=P*(P-1), x，y一定存在正整數解，換句話說當兩個石子之間的距離大於等於T*(T-1)時，中間有相當大的距離是每個點都可以跳到的，因為沒有石子，所以對答案沒有貢獻，可以取模(%90),這樣就很好辦了。。。於是我們就成功地把狀態給壓縮了。

注意：石子並沒有按順序給出要排序。

代碼：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define inf 1<<30
using namespace std;
int l,s,t,m,f[900000],pos[200],a[900000];
void slove(){
    int ans=0;
    for(int i=1;i<=m;i++)
        if(pos[i]%s==0) ans++;
    printf("%d",ans);
}
int main()
{
    scanf("%d%d%d%d",&l,&s,&t,&m);
    for(int i=1;i<=m;i++)
        scanf("%d",&pos[i]);
    sort(pos+1,pos+m+1);
    if(s==t){
        slove();
        return 0;
    }
    for(int i=1;i<=m;i++){
        int temp=pos[i]-pos[i-1];
        pos[i]=pos[i-1]+temp%90;
    }
    l=pos[m]+(l-pos[m])%90;
    for(int i=1;i<=m;i++)
        a[pos[i]]=1;
    for(int i=1;i<=l;i++)
        f[i]=inf;
    f[0]=0; 
    for(int i=1;i<=l;i++)
        for(int j=s;j<=t;j++)
            if(i-j>=0)
                f[i]=min(f[i-j]+a[i],f[i]);
    printf("%d",f[l]);
}