題目：
https://www.luogu.org/problem/show?pid=1203

標簽是搜索和動態(tài)規(guī)劃……；

O(n^2)純模擬;

這個題交了三遍才A；

思路：
記兩個數(shù)組；Next和pre；
然后模擬；

坑：
1.第一次交56分，沒有判全是相同的情況，以及走重的情況；
2.第二次交67分，因為沒有考慮以w為起點的情況；
當以w為起點是，它可以看做r，也可以看做b，需要分別計數(shù)；

總結：
1.要想全情況；
2.讀準題意！

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int MAXN=1001; int n,sta,en,ans,cnt; int Next[MAXN],pre[MAXN]; bool vis[MAXN]; char s[MAXN],c;void init() {for(int i=2;i<n;i++) Next[i]=i+1,pre[i]=i-1;Next[n]=1,Next[1]=2,pre[1]=n,pre[n]=n-1; }void calc(int k) {for(int j=k;;j=Next[j]){if(!vis[j] && (s[j]==c || s[j]=='w')) vis[j]=1,cnt++;// else if(!vis[j] && c=='w') vis[j]=1,cnt++;else break;}c=s[pre[k]];//并不是i-1,因為1也可以和n作為斷開點；for(int j=pre[k];;j=pre[j]){if(!vis[j] && (s[j]==c || s[j]=='w')) vis[j]=1,cnt++;// else if(!vis[j] && c=='w') vis[j]=1,cnt++;else break;} }void solve() {scanf("%d%s",&n,s+1);init();int len=strlen(s+1);for(int i=1;i<=n;i++)//枚舉斷開點;{ memset(vis,0,sizeof(vis));c=s[i],cnt=0;if(c=='w'){c='r',calc(i);memset(vis,0,sizeof(vis)),cnt=0;c='b',calc(i);}else calc(i);ans=max(ans,cnt);if(cnt==n) break;}cout<<ans; }int main() {solve();return 0; }

總結

以上是生活随笔為你收集整理的洛谷 1203 [USACO1.1]坏掉的项链Broken Necklace的全部內容，希望文章能夠幫你解決所遇到的問題。

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