Climber.pI的OI之路

Feedback

# re: NOIp 2005 過河 2010-10-09 08:53 ftiasch

2520恰好是1, 2, ..., 10的最小公倍數。原理就是可以證明說狀態函數的值肯定會出現大段的重復。在理論上可以保證的就是2520。更多的分析應該用裴蜀定理來做。  回復  更多評論   

# re: NOIp 2005 過河 2011-09-08 13:30 PZYR

#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXN 1000000;
bool L[200000] = {0};
int f[200000] = {0}, stone[110] = {0};
int min(int x, int y){return x < y ? x : y;}
void swap(int x, int y){
int k = stone[x];
stone[x] = stone[y];
stone[y] = k;
}
int main(){
int l, S, T, M, i, j;
scanf("%d%d%d%d", &l, &S, &T, &M);
for (i = 1; i <= M; i++) scanf("%d", &stone[i]);
stone[0] = 0;
for (i = 1; i < M; i++)
for (j = i+1; j <= M; j++)
if (stone[i] > stone[j]) swap(i, j);
stone[++M] = l;
for (i = 1; i <= M; i++){
while (stone[i] - stone[i-1] > 2520) stone[i] -= 2520;
if (i != M) L[stone[i]] = 1;
}
l = stone[M--];
for (i = 0; i <= l; i++) f[i] = MAXN; f[0] = 0;
for (i = 0; i < l; i++)
for (j = S; j <= T; j++){
int k = i+j;
if (i + j >= l) k = l;
f[k] = min(f[k], f[i]+L[i]);
}
printf("%d\n", f[l]);
}  回復  更多評論