- 首页 > it技术 > >
NOIP|Noip 2005 过河 - DP - 离散化
#include
#include
#include
#include
using namespace std;
#define debug(x) cerr << #x << "=" << x << endl;
const int MAXN = 10000000 + 10;
const int INF = 1<<30 - 1;
int l,s,cnt,t,m,a[MAXN],ans,dp[MAXN],b[MAXN];
int main() {
cin >> l;
cin >> s >> t >> m;
for(int i=1;
i<=m;
i++)
cin >> a[i];
if(s == t) {
int tot = 0;
for(int i=1;
i<=m;
i++)
if(a[i] % s == 0)
tot++;
cout << tot << endl;
return 0;
}
sort(a+1,a+m+1);
for(int i=1;
i<=m;
i++) {
int dis = a[i] - a[i-1];
a[i] = a[i-1] + dis%100;
b[a[i]] = 1;
}
l = (l - a[m]) % 100 + a[m];
for(int i=1;
i<=m;
i++)
b[a[i]]=1;
memset(dp,0x3f,sizeof(dp));
dp[0] = 0;
for(int i=s;
i<=l+t;
i++)
for(int k=s;
k<=t;
k++)
if(i - k >= 0)
dp[i] = min(dp[i], dp[i-k] + b[i]);
int ans = INF;
for(int i=l;
i<=l+t;
i++)
ans = min(ans, dp[i]);
cout << ans;
return 0;
}
推荐阅读
