2018-3-25

昨天晚上有人評論了我的博客，有點小激動，今天就把自己之前寫的博客整理了一下，發現自己USACO里面有一道題目沒有寫博客…于是乎把它給補上。

題目大意：

給你一串項鏈，白色，藍色，紅色，白色可以替換為任意顏色，從某個地方， 剪短該項鏈，問你從兩邊所能得到的珠子和的最大值為多少，每一邊得到的 珠子數為到第一個不同顏色的珠子截止（w色可以進行替換）。

我們最容易想到的，就是枚舉從每一個地方剪斷所能獲得的兩邊的和，然后求得最大值。需要我們注意的就是該題目給我們的是一個環。

/* ID: 18795871 PROG: beads LANG: C++ */ #include<iostream> #include<fstream> using namespace std;ifstream fin("beads.in"); ofstream fout("beads.out");const int N = 350; char x[2*N+10],y[2*N+10]; int lef[N+10],rig[N+10]; int n;int main(){int i,j;while (fin>>n){fin>>x;for (i=0;i<n;i++){x[i+n]=x[i];}for (i=0;i<2*n;i++){y[2*n-i-1]=x[i];}for (int i=0;i<=n;i++) lef[i]=1;for (int i=0;i<=n;i++) rig[i]=1;int cnt; for (i=0;i<=n;i++){char f=x[i];for (j=i+1;j<2*n;j++){if (x[j]==f){lef[i]++;}else{if (f=='w'){f=x[j];lef[i]++;}else if (x[j]=='w'){lef[i]++;}else{break;}}}}for (i=0;i<=n;i++){char f=y[i];for (j=i+1;j<2*n;j++){if (y[j]==f){rig[i]++;}else{if (f=='w'){f=y[j];rig[i]++;}else if (y[j]=='w'){rig[i]++;}else{break;}}}}int ma=0;for (int i=0;i<=n;i++){ma=max(ma,lef[i]+rig[n-i]);}if (ma>n) fout<<n<<endl;else fout<<ma<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的USACO-Section1.2 Broken Necklace （枚举法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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