caioj1522: [NOIP提高組2005]過河

狀態壓縮的經典題。

按照一般做法，DP一維時間O(n)，顯然跑不過。考慮到石子較少，實際上有很長一段是一定可以跳到的，設兩個石頭分別在i點和j點，跳躍的路程為S到T。那么從i點可以跳到i+S到i+T。從j-T到j-S可以跳到J。顯然當i和j相隔非常非常遠時，從i到i+T中必然可以經過若干次跳躍，然后跳到j-T到j的任意一段。

然后狀壓，可以發現距離大于90(假設s和t不同，s(9)和t(10)的最小公倍數)一定可以到達，這樣我們把石頭之間的距離%90節省時間。

然后特判一下s==t的情況，就可以AC。但有一個問題，我將mod變成100，不特判s==t的情況，這樣會WA，這個我無法理解。

?

數據：10000
7 7 100
1111 1118 1114 1117 3010 7508 1119 1105 899 1112 9667 3238 1108 5178 4627 2116 2089 9184 1115 8887 3565 3560 3559 3562 2410 3564 3571 565 3561 3566 3573 7432 9485 4484 7258 4555 8812 1291 3567 3221 5252 5253 5244 797 5251 7885 5245 9340 5255 6537 7737 5243 9316 5246 6694 6773 5247 6031 5256 5249 5484 5482 7513 5485 5479 5481 5480 5489 381 2572 9255 7624 5821 8606 7829 5488 442 5490 5492 8098 483 482 481 478 469 474 4054 472 471 4407 479 7006 475 470 3147 6933 9097 7781 473 2221
應該輸出10但是改了輸出13.

?

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int se[110],a[1100000],f[1100000];
int main()
{int L,s,t,n;scanf("%d%d%d%d",&L,&s,&t,&n);for(int i=1;i<=n;i++)scanf("%d",&se[i]);sort(se+1,se+n+1);if(s==t){int ans=0;for(int i=1;i<=n;i++)if(se[i]%s==0)ans++;printf("%d\n",ans);return 0;}for(int i=1;i<=n;i++)se[i]=se[i-1]+(se[i]-se[i-1])%90;L=(L-se[n])%90+se[n];for(int i=1;i<=n;i++)a[se[i]]=1;memset(f,63,sizeof(f));f[0]=0;for(int i=s;i<=L+t;i++)for(int j=s;j<=t;j++)if(i>=j)f[i]=min(f[i],f[i-j]+a[i]);int ans=999999999;for(int i=L;i<L+t;i++)ans=min(ans,f[i]);printf("%d\n",ans);return 0;
}

?