/* ID: wuqi9395@126.com PROG: beads LANG: C++ */ // O(n^2) #include<iostream> #include<fstream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stack> #include<vector> #include<set> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) #define maxn 1000 #define INF 1<<25 #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; using namespace std; int main () { string str; int n, i, l, r, mx = 0; ifstream fin ("beads.in"); ofstream fout ("beads.out"); fin>>n; fin>>str; str += str; for (i = 0; i < n; i++) { l = r = 1; int k = i + 1; char flag; while(l < n) { int j = i; while(str[j] == ‘w‘) j++; flag = str[j]; if (str[k] == flag || str[k] == ‘w‘) k++, l++; else break; } k = i + n - 2; while(r < n) { int j = i; while(str[j] == ‘w‘) j--; flag = str[j]; if (str[k] == str[i + n - 1] || str[k] == ‘w‘) k--, r++; else break; } if (l + r > mx) mx = l + r; } if (mx > n) mx = n; fout<<mx<<endl; return 0; }
r[0] = p[0] = 0 If c = ‘r‘ then r[p+1] = r[p] + 1 and b[p+1] = 0 because the length of the blue beads is 0. if c = ‘b‘ then b[p+1] = b[p] + 1 and r[p+1] = 0 if c = ‘w‘ then both length of the red and length of blue beads can be longer. so r[p+1] = r[p]+1 and b[p+1] = b[p] + 1.
/* ID: wuqi9395@126.com PROG: beads LANG: C++ */ // O(N) DP #include<iostream> #include<fstream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stack> #include<vector> #include<set> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) #define maxn 1000 #define INF 1<<25 #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; using namespace std; int main () { ifstream fin ("beads.in"); ofstream fout ("beads.out"); int i, j, n, mx = 0; int left[810][2] = {0}, right[810][2] = {0}; string str; fin>>n>>str; str += str; for (i = 1; i <= 2 * n; i++) { if (str[i - 1] == ‘r‘) left[i][0] = left[i - 1][0] + 1, left[i][1] = 0; else if (str[i - 1] == ‘b‘) left[i][1] = left[i - 1][1] + 1, left[i][0] = 0; else left[i][1] = left[i - 1][1] + 1, left[i][0] = left[i - 1][0] + 1; } for (i = 2 * n - 1; i >= 0; i--) { if (str[i] == ‘r‘) right[i][0] = right[i + 1][0] + 1, right[i][1] = 0; else if (str[i] == ‘b‘) right[i][1] = right[i + 1][1] + 1, right[i][0] = 0; else right[i][1] = right[i + 1][1] + 1, right[i][0] = right[i + 1][0] + 1; } for (i = 0; i < 2 * n; i++) mx = max(mx, max(left[i][0], left[i][1]) + max(right[i][0], right[i][1])); mx = min(mx, n); fout<<mx<<endl; return 0; }
[USACO Training] Broken Necklace
原文:http://blog.csdn.net/sio__five/article/details/18524267