SRM 521
Problem Solving/TopCoder logs 2011. 10. 24. 01:08
오랜만에 참가했다..
요즘 다리를 다쳐서 컨디션도 안좋은데.. 스름도 망쳤다..
덕분에 다시 blue 로 떨어지고.. 젠장.. 괜히 참가했다..
ㅠ_ㅠ
250 문제는 당연히 DP 구나 하고 마구 풀었는데.. 나중에 남들 코드 보고 화들짝 놀랐다.. -_-
아주 간단한 greedy 해결방법이 있었다.. 어쩐지 다들 빨리 풀더라니..
나이를 먹다보니.. 뭔가 참신한 생각이 안나온다..
요즘 다리를 다쳐서 컨디션도 안좋은데.. 스름도 망쳤다..
덕분에 다시 blue 로 떨어지고.. 젠장.. 괜히 참가했다..
ㅠ_ㅠ
250 문제는 당연히 DP 구나 하고 마구 풀었는데.. 나중에 남들 코드 보고 화들짝 놀랐다.. -_-
아주 간단한 greedy 해결방법이 있었다.. 어쩐지 다들 빨리 풀더라니..
나이를 먹다보니.. 뭔가 참신한 생각이 안나온다..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 #define min(x, y) ((x) > (y) ? (y) : (x))
8 //#define max(x, y) ((x) > (y) ? (x) : (y))
9 #define INF 999999999
10 //#define EPS 1e-14
11
12 int memo[100][100];
13 int len;
14 string str;
15
16 int recur(int l, int r)
17 {
18 int res, temp, i;
19 if (l == r)
20 return 1;
21 if (l > r)
22 return 0;
23 if (memo[l][r] != -1)
24 return memo[l][r];
25 res = INF;
26 if (str[l] == '(' && str[r] == ')') {
27 temp = recur(l+1, r-1);
28 if (temp < res)
29 res = temp;
30 }
31 else {
32 temp = min(recur(l+1, r) + 1, recur(l, r-1) + 1);
33 if (temp < res)
34 res = temp;
35 }
36 for (i = l; i < r; i++) {
37 temp = recur(l, i) + recur(i+1, r);
38 if (temp < res)
39 res = temp;
40 }
41 return memo[l][r] = res;
42 }
43
44 class MissingParentheses {
45 public:
46
47 int countCorrections(string par)
48 {
49 int res;
50 str = par;
51 len = str.size();
52 memset(memo, -1, sizeof(memo));
53 res = recur(0, len-1);
54 return res;
55 }
56
57 };
'Problem Solving > TopCoder logs' 카테고리의 다른 글
| TCO13 Round 1C 생명연장 매치 (0) | 2013.03.10 |
|---|---|
| TCO12 R1A - 606등 -_-;; (0) | 2012.04.01 |
| SRM 529 (0) | 2012.01.15 |
| SRM 511 (0) | 2011.07.04 |
| TCO11 R1 - 탈락 (0) | 2011.06.23 |
| SRM 509 !! (0) | 2011.06.09 |
| SRM 507 - 나이스! (0) | 2011.05.30 |
| TCO11 Qual2 (0) | 2011.05.20 |
| TCO11 Qual1 (2) | 2011.05.15 |
| SRM 504 - unrated event (0) | 2011.04.27 |