原題傳送：http://acm.hdu.edu.cn/showproblem.php?pid=3474

　　單調隊列。

　　這題的模型可以這樣描述：給一個只由1和-1組成的循環序列，求以每個點為起點且長度最長為n的子串的最小值。到這一步，應該能想到單調隊列的解法了。

View Code 1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #define N 2000005 5 6 int sum[N], a[N], q[N], n, ok1[N], ok2[N]; 7 8 void cal(int ok[]) 9 { 10 int i, head, tail, t = 2 * n; 11 12 for(i = 1; i <= t; i ++) 13 sum[i] = sum[i - 1] + a[i]; 14 15 for(head = tail = 0, i = 1; i < n; i ++) 16 { 17 while(head < tail && sum[i] <= sum[q[tail - 1]]) 18 tail --; 19 q[tail++] = i; 20 } 21 22 for(i = n; i <= t; i ++) // 這里i是區間右端點 23 { 24 while(head < tail && q[head] < i - n + 1) 25 head++; 26 while(head < tail && sum[i] <= sum[q[tail - 1]]) 27 tail--; 28 q[tail++] = i; 29 30 ok[i - n] = (sum[q[head]] - sum[i - n] >= 0); 31 } 32 } 33 34 int main() 35 { 36 int t, i, ans, cas; 37 char c; 38 scanf("%d\n", &t); 39 for(cas = 1; cas <= t; cas ++) 40 { 41 for(n = 0; (c = getchar()) != '\n';) 42 a[++n] = (c == 'C' ? 1 : -1); 43 44 for(i = 1; i <= n; i ++) 45 a[n + i] = a[i]; 46 47 cal(ok1); 48 49 std::reverse(a + 1, a + 2 * n + 1); // 算另一個方向 50 cal(ok2); 51 52 for(ans = 0, i = 1; i <= n; i ++) 53 ans += ok1[i] | ok2[n - i]; 54 printf("Case %d: %d\n", cas, ans); 55 } 56 return 0; 57 }

轉載于:https://www.cnblogs.com/huangfeihome/archive/2012/10/17/2728501.html

總結

以上是生活随笔為你收集整理的HDU3474 Necklace的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。