題目描述
祖瑪是一款著名的益智類游戲，玩家控制發(fā)射器發(fā)射小球，有三個或三個以
上顏色相同的小球相連即可消去，消去之后兩邊的小球會自動接在一起，若產(chǎn)
生了連續(xù)大于等于三個顏色相同的小球，還會繼續(xù)消去。

如果通過上面的敘述你仍沒有明白游戲規(guī)則，你可以點擊 鏈接 體驗。
現(xiàn)給出一串長度為 n 的小球，即有 n + 1 個位置供玩家發(fā)射，保證沒有連續(xù)
三個相同顏色的小球。玩家能在任意位置發(fā)射任意顏色的小球，但只能發(fā)射一
顆，或者不發(fā)射。你的目標是要使得這串小球的長度最小。
輸入
第一行包括一個正整數(shù) n(n ≤ 5000) ，表示小球的長度。
第二行包括 n 個數(shù) ai(0 ≤ ai ≤ 109) ，表示小球的顏色。
輸出
一個整數(shù)，代表最小的長度。
May 10, 2020 2
2020 年西電程序設計競賽網(wǎng)絡賽
樣例
樣例輸入 樣例輸出
5
1 1 0 0 1
0
樣例解釋
將這六個位置標記為 1 ～ 6 ，(1) ? (2) ? (3) ? (4) ? (5) ? (6)。 在 3 、4 、5 位置中任選一個，發(fā)射一顆顏色為 0 的球即可將整串小球消去。
思路：數(shù)據(jù)量不大，可以直接模擬，不需要記憶化之類的。注意判斷邊界情況。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=5e3+100; int a[maxx]; int n;inline int judge(int u,int num) {int len=0;int l,r;if(a[u]==a[u+1]) r=u+2,l=u-1;else if(a[u]==a[u-1]) r=u+1,l=u-2;else if(u+2<=n&&a[u+1]==a[u+2]) l=u,r=u+3;else return 0;len=2;while(1){if(l==0||r==n+1) break;if(a[l]!=a[r]) break;int num=a[l];int cnt=0;while(l>=1&&a[l]==num) l--,cnt++;while(r<=n&&a[r]==num) r++,cnt++;if(cnt>2) len+=cnt;else break;}return len; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);int _max=0;for(int j=1;j<n;j++) _max=max(_max,max(judge(j,a[j]),judge(j,a[j+1])));if(a[1]==a[2]) _max=max(_max,2);else if(a[n]==a[n-1]) _max=max(_max,2);printf("%d\n",n-_max);return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的2020年第十八届西电程序设计竞赛网络预选赛之Problem B 祖玛 1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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