?

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5455

?

題目大意：定義遞推式 F為f(0)='f',f(1)='ff',f(2)='cff',f(n)=f(n-1)+'f'，給出一個首位相連的字符串s，問組成s至少需要多少個F，如果F不能組成s，輸出-1.

分析：很明顯我們有：

（1）如果字符串含有除c和f外的其他字符的話，那么輸出-1，如果3倍c的數量大于字符串s的長度，也輸出-1.

（2）如果字符串只含有f，那么結果為(len+1)/2，len為字符串s的長度.

（3）對于其他情況，我們紀錄每一個c出現的位置，然后從后往前遍歷，如果c[i]-c[i-1]>2的話，那么就說明這兩個c之間含有大于等于2個的f，計數器加1，否則標記不可能.

　　　　對于第一個c之前和最后一個c之后的部分，如果相加有大于等于2個f的話，(同樣這一步也可以判斷如果只有一個c的話并且c[0]+len-c[k-1]>2也就是字符串s長度大于2)計數器再加1，否則標記不可能。

實現代碼如下：

#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #include<vector> #include<queue> #include<algorithm>using namespace std; typedef long long LL;const int maxn=1000005; const int INF=0x3f3f3f3f;char str[maxn]; int cnt[maxn];int main() {int T, cas=1;scanf("%d", &T);while(T--){scanf("%s", str);int len=strlen(str);int k=0;int flag=1;for(int i=0; i<len; i++){if(str[i]=='c')cnt[k++]=i;if(str[i]!='c'&&str[i]!='f')flag=0;}printf("Case #%d: ", cas++);if(!flag || k*3>len){puts("-1");continue;}if(!k){printf("%d\n", (len+1)/2);continue;}int ans=0;for(int i=k-1; i>0; i--){if(cnt[i]-cnt[i-1]>2)ans++;else{flag=0;break;}}///對于第一個c之前和最后一個c之后的部分，///如果相加有大于等于2個f的話，(同樣這一步也可以判斷如果只有一個c的話并且c[0]+len-c[k-1]>2也就是字符串s長度大于2)計數器再加1，if(cnt[0]+len-cnt[k-1]>2)ans++;else flag=0;///否則標記不可能if(flag)printf("%d\n", ans);elseputs("-1");}return 0; }

?

轉載于:https://www.cnblogs.com/w-y-1/p/5772138.html

總結

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

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