其實這題算動態規劃有點牽強，因為它最大的難點和突破點在于把問題進行轉化。我的做法是，先數出字符串的總數total和'A'的數目anum，然后只要在字符串中找出長度為anum的連續一段，它的'A'數最多就行了(假設是maxnum，則最后結果就是anum-maxnum)。找這個包含最多'A'的段才用到動態規劃，其實挺簡單的，就是循環一次記錄從每個點起始往右長度為anum的段中'a'的數目即可。

/** hdu3819/win.cpp* Created on: 2012-10-29* Author : ben*/ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <queue> #include <set> #include <map> #include <stack> #include <string> #include <vector> #include <deque> #include <list> #include <functional> #include <numeric> #include <cctype> using namespace std; const int MAXN = 100005; char str[MAXN]; int anum, total, ans[MAXN];int main() { #ifndef ONLINE_JUDGEfreopen("data.in", "r", stdin); #endifint T;scanf("%d", &T);getchar();for(int t = 1; t <= T; t++) {printf("Case %d: ", t);gets(str);total = strlen(str);anum = count(str, str + total, 'A');if(anum <= 1) {puts("0");continue;}fill(ans, ans + MAXN, 0);ans[0] = count(str, str + anum, 'A');for(int i = 1; i < total; i++) {ans[i] = ans[i - 1];if(str[i - 1] == 'A') {ans[i]--;}if(str[(i + anum - 1) % total] == 'A') {ans[i]++;}}int result = *max_element(ans, ans + total);printf("%d\n", anum - result); // printf("anum = %d, total = %d\n", anum, total); }return 0; }

轉載于:https://www.cnblogs.com/moonbay/archive/2012/10/29/2744970.html

總結

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

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