LightOJ - 1017 - Brush (III)

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long LL;
4. const int S = 103;
5. const int MOD = 1000000007;
6. int _I(){int x; scanf("%d", &x); return x;}
7. LL _LL(){LL x; scanf("%lld", &x); return x;}
8. int dirX[]={1, 0, -1, 0, 1, -1, 1, -1};
9. int dirY[]={0, 1, 0, -1, 1, -1, -1, 1};
10. int rX[] = {1, 1, 2, 2, -1, -1, -2, -2};
11. int rY[] = {2, -2, 1, -1, 2, -2, 1, -1};
12.  
13. int sset(int N, int pos){return N=N|(1<<pos);}
14. bool check(int N, int pos){return (bool)(N&(1<<pos));}
15. int reset(int N, int pos){return N=N&~(1<<pos);}
16. ///...............Code Starts From Here...............///
17.  
18. int yc[S];
19. int dp[S][S];
20. int w, n, k;
21.  
22.  
23. int brush3(int ind, int movee){
24.     if(movee > k)return 0;
25.     if(ind == n)return 0;
26.     if(dp[ind][movee] != -1)return dp[ind][movee];
27.     dp[ind][movee] = 1;
28.     int i;
29.     for(i = ind+1; (i < n && abs(yc[ind]-yc[i]) <= w); i++){
30.         dp[ind][movee] += 1;
31.     }
32.     dp[ind][movee] += brush3(i, movee+1);
33.     dp[ind][movee] = max(dp[ind][movee], brush3(ind+1, movee));
34.     return dp[ind][movee];
35. }
36.  
37. void Do(){
38.     int t = _I(), cs = 0;
39.     while(t--){
40.         memset(dp, -1, sizeof(dp));
41.         n = _I();
42.         w = _I();
43.         k = _I();
44.         for(int i = 0; i < n; i++){
45.             int z = _I();
46.             yc[i] = _I();
47.         }
48.         sort(yc, yc+n);
49.         int ans = brush3(0, 1);
50.         printf("Case %d: %d\n", ++cs, ans);
51.     }
52. }
53.  
54. int main(){
55.     Do();
56.     return 0;
57. }