題目描述

你有一條由N個紅色的，白色的，或藍色的珠子組成的項鏈(3<=N<=350)，珠子是隨意安排的。 這里是 n=29 的二個例子:

第一和第二個珠子在圖片中已經被作記號。

圖片 A 中的項鏈可以用下面的字符串表示：

brbrrrbbbrrrrrbrrbbrbbbbrrrrb

假如你要在一些點打破項鏈,展開成一條直線，然后從一端開始收集同顏色的珠子直到你遇到一個不同的顏色珠子，在另一端做同樣的事(顏色可能與在這之前收集的不同)。 確定應該在哪里打破項鏈來收集到最大數目的珠子。

例如，在圖片 A 中的項鏈中，在珠子 9 和珠子 10 或珠子 24 和珠子 25 之間打斷項鏈可以收集到8個珠子。

白色珠子什么意思?

在一些項鏈中還包括白色的珠子(如圖片B) 所示。

當收集珠子的時候，一個被遇到的白色珠子可以被當做紅色也可以被當做藍色。

表現含有白珠項鏈的字符串將會包括三個符號 r ， b 和 w 。

寫一個程序來確定從一條被給出的項鏈可以收集到的珠子最大數目。

輸入輸出格式

輸入格式：

第 1 行: N, 珠子的數目

第 2 行: 一串長度為N的字符串, 每個字符是 r ， b 或 w。

輸出格式：?

輸入輸出樣例

輸入樣例#1：
29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb 輸出樣例#1：
11

說明

題目翻譯來自NOCOW。

USACO Training Section 1.1

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

搜索太沒意思了，就開始用DP做死，線性復雜度就可以；

先確定不是全一樣

f ?：從i開始　　d：到i結束

0 ：紅色　　　1 ：藍色

找到一個r與b的分界點，從它開始愉快的掃描更新就可以了

因為是環狀，自己yy了一個loop標記，反正實現循環了

［PS］：貌似人家爆搜的時間和我差不多，N太小了，唉

?

// // main.cpp // usaco1.1 // // Created by abc on 16/8/14. // Copyright ? 2016年 abc. All rights reserved. // #include <iostream> #include <cstdio> #include <cmath> using namespace std; const int N=400; int n,ans=1; char c[N]; int f[N][2],d[N][2],only=0; //only 0--->all same //0 red 1 blue inline int nxt(int i){return (i+1)%n; } inline int lst(int i){return (i-1+n)%n; } void init(){for(int i=0;i<n;i++) if(c[i]=='r') only=1;if(only==0) return;for(int i=0;i<n;i++) if(c[i]=='b') only=1;if(only==0) return;int st=0;for(int i=1;i<n;i++) if(abs(c[i]-c[i-1])==16) {st=i-1;break;}bool loop=0;for(int i=st;loop==0||i!=st;i=lst(i)){//printf("for1 %d\n",i);loop=1;if(c[i]=='r') f[i][0]=f[nxt(i)][0]+1,f[i][1]=0;if(c[i]=='b') f[i][1]=f[nxt(i)][1]+1,f[i][0]=0;if(c[i]=='w') f[i][0]=f[nxt(i)][0]+1,f[i][1]=f[nxt(i)][1]+1;}st++;loop=0;for(int i=st;loop==0||i!=st;i=nxt(i)){//printf("for2 %d\n",i);loop=1;if(c[i]=='r') d[i][0]=d[lst(i)][0]+1,d[i][1]=0;if(c[i]=='b') d[i][1]=d[lst(i)][1]+1,d[i][0]=0;if(c[i]=='w') d[i][0]=d[lst(i)][0]+1,d[i][1]=d[lst(i)][1]+1;}} int main(int argc, const char * argv[]) {scanf("%d",&n);for(int i=0;i<n;i++) cin>>c[i];init();if(only==0) ans=n;else for(int i=0;i<n;i++){int t=max(f[i][0]+d[lst(i)][1],f[i][1]+d[lst(i)][0]);ans=max(ans,t);}cout<<ans;}

?

總結

以上是生活随笔為你收集整理的USACO1.1Broken Necklace[环状DP作死]的全部內容，希望文章能夠幫你解決所遇到的問題。

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