定长线段可覆盖的点的个数

给定一系列x轴的点坐标，例如 1，3，7，8，9，11这些坐标升序放在数组中，现在给一根绳子，长度为4，问绳子最多能覆盖的点数有多少，例如绳子放前面只能覆盖两个点，1,3，如果放后面能覆盖4个点

 

简单DP.其实也不是十分简单。还得想会儿。设绳长为line, 若包含下标为i的点，往前扩展，最远的可覆盖的点的下标为f(i)

那么，

每次i后移一位，

若 input[i+1] - input[i] <= line

     f(i+1) = f(i)

否则

     f(i+1)  = t, t = min{ f(i) .. i+1} where input[i+1] - input[t]

 

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAX 1000

int getMaxCount(int *input, int size, int line){
    if(input == NULL || size <= 0 || line == 0) return 0;
    int last = 0;
    int i = 1;
    int max = 1;
    for(;i<size;i++){
        if(input[i] - input[last] <= line){
            max = max>(i-last+1)? max:(i-last+1);
            continue;
        }
        while(input[i]-input[last]>line)
            last++;
    }
    return max;

}

int main(){
    int input[] = {1,2,7,8,9,11};
    int line = 4;
    int max = getMaxCount(input, sizeof(input)/sizeof(int), line);
    printf("%d \n", max);
}

阅读(851) | 评论(0) | 转发(1) |

0

上一篇：Poj2092:字符串拉链

下一篇：单链表的快排