LightOJ - 1033 - Generating Palindromes

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long LL;
4. const int S = 100003;
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. char palin[101];
19. int dp[101][101];
20.  
21. int generatePalin(int low, int high){
22.     if(low >= high)return 0;
23.     if(dp[low][high] != -1)return dp[low][high];
24.     dp[low][high] = 0;
25.     if(palin[low] == palin[high])dp[low][high] = generatePalin(low+1, high-1);
26.     else dp[low][high] = min(1+generatePalin(low+1, high), 1+generatePalin(low, high-1));
27.     return dp[low][high];
28. }
29.  
30. void Do(){
31.     int t = _I(), cs = 0;
32.     while(t--){
33.         scanf("%s", palin);
34.         memset(dp, -1, sizeof(dp));
35.         int sz = strlen(palin)-1;
36.         int ans = generatePalin(0, sz);
37.         printf("Case %d: %d\n", ++cs, ans);
38.     }
39. }
40.  
41. int main(){
42.     Do();
43.     return 0;
44. }

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. }