sicily 1148 dp

//本来想水水题的，没想到被它水了很久很久。。 //给独木桥上石头的分布，青蛙每次只能跳[s,t]，求过桥踩到最少石头数 //数据太大压缩做dp就可以过 //wengsht #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int l,s,t,m,k; int st[111]; int reduce[111]; //各石头压缩数 int dp[5000]; //理论上数组开到50000。。用小号刷到5000，数据比较水 int isst[5000]; bool path[5000]; //踩过 int main() { //freopen("1.txt","r",stdin); cin>>l>>s>>t>>m; for( int i = 1;i <= m;i++ ) cin>>st[i]; sort( st,st+m+1 ); for( int i = 1;i <=m;i++ ) { reduce[i] += reduce[i-1]; //超过t*t t 的话 压缩: if( st[i] - st[i-1] - t*t > t ) reduce[i] += (st[i] - st[i-1] - t*t)/t*t; } for( int i = 1;i <= m;i++ ) { st[i] -= reduce[i]; isst[st[i]] = 1; } memset( dp,0x7f,sizeof(dp) ); dp[0] = 0; path[0] = true; //dp很简单 for( int i = 0;i <= st[m];i++ ) { if( !path[i] ) continue; for( int j = s;j <= t;j++ ) { path[i+j] = true; if( dp[i+j] > dp[i] + isst[i+j] ) dp[i+j] = dp[i] + isst[i+j]; } } int result = 101; for( int i = st[m]+1; i <= st[m]+t; i++ ) { if( path[i] && result > dp[i] ) result = dp[i]; } cout<<result<<endl; return 0; }