跳至正文

NOIP 过河 解题报告

这题我不怎么说吧,我在网上搜的,到现在为止为什么能这样我还是没想通,只知道这样能过。
就当是个定理吧,记住就是了,这题我不太想解释,看代码吧:

#include <stdio.h>
#define INT_MAX 200000000
int stone[100];
int map[9190], f[9190];

int com(const void *a, const void *b){ return *(int *)a - *(int *)b; }

int main(void)
{
 int i, j, k;
 int l, s, t, n;
 int p, jmp = 0;
 int ans = 0;

 scanf(%d%d%d%d, &l, &s, &t, &n);
 for(i = 0; i <= 9190; i++){
 f[i] = INT_MAX;
 }
 f[0] = 0;
 for(i = 0; i < n; i++){
 scanf(%d, &stone[i]);
 }
 if(s == t){
 for(i = 0; i < n; i++){
 if(stone[i] % s == 0){
 ans++;
 }
 }
 printf(%d\\n, ans);
 return 0;
 }
 qsort(stone, n, sizeof(int), com);
 k = 0;
 for(i = 0; i < n; i++){
 p = stone[i] - k - 1;
 if(p >= s * t){
 jmp += p - s * t;
 }
 map[stone[i] - jmp] = 1;
 k = stone[i];
 }
 if(l - k > s*t){
 jmp += l - k - s*t;
 }
 l -= jmp;
 for(i = 0; i <= l; i++){
 if(f[i] == INT_MAX){
 continue;
 }
 for(j = s; j <= t; j++){
 if(f[i + j] > f[i] + map[i + j]){
 f[i + j] = f[i] + map[i + j];
 }
 }
 }
 for(i = l, ans = INT_MAX; i <= l + t - 1; i++){
 if(ans > f[i]){
 ans = f[i];
 }
 }
 printf(%d\\n, ans);

 return 0;
}

发表回复

您的电子邮箱地址不会被公开。