light oj 1084 线性dp

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 #define ll long long
 7 
 8 using namespace std;
 9 const int N = 1e5+1000;
10 
11 int a[N],dp[N];
12 
13 void solve()
14 {
15     int n,k;
16     scanf("%d %d",&n,&k);
17     for(int i = 0; i < n; i++)
18     {
19         scanf("%d",&a[i]);
20     }
21     sort(a,a+n);
22     memset(dp,0,sizeof(dp));
23     for(int i = n-1; i >= 0; i--)
24     {
25         dp[i] = 0x3f3f3f;
26         int j = upper_bound(a,a+n,a[i]+2*k)-a;
27         if(j - i >= 3) dp[i] = min(dp[j]+1,dp[i]);
28         if(j - i >= 4) dp[i] = min(dp[j-1]+1,dp[i]);
29         if(j - i >= 5) dp[i] = min(dp[j-2]+1,dp[i]);
30     }
31     if(dp[0] == 0x3f3f3f)
32         printf("-1\n");
33     else
34         printf("%d\n",dp[0]);
35 }
36 
37 int main(void)
38 {
39     int t,cnt = 0;
40     scanf("%d",&t);
41 
42     while(t--)
43     {
44         printf("Case %d: ",++cnt);
45         solve();
46     }
47     return 0;
48 }