1032: [JSOI2006]祖码Zuma

链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1032

Description

那是叁个风行在Jsoi的游艺,名叫Zuma。精致细腻的背景,外加神秘的印加音乐烘托,犹如献身在古旧的国度里面,举办二个潜在的嬉戏——那便是有名的Zuma游戏。Zuma游戏的出类拔萃是三头深绿蛙,深紫藤色蛙会退掉种种颜色的珍珠,珠子造型精彩,並且具备神秘的色彩,环绕着樱桃红蛙的是载着珠子的准绳,各个颜色的珠子会顺着轨道往前滑行,橄榄绿蛙必得遏止珠子们滚进去轨道终点的洞里头,怎么样压缩珠子呢?就得要靠浅绿蛙吐出的珍珠与法规上的珠子相结合,颜色相通者即能够灭亡得分!直到轨道上的珍珠通通都被清到底为止。
大概你并连发解Zuma游戏。无妨。这里大家介绍叁个粗略版本的Zuma游戏准则。一条通道中有局地玻璃珠,每一个珠子有独家的颜料,如图1所示。游戏的使用者能够做的是采取大器晚成种颜色的珍珠(注意:颜色可以任选,那与忠诚游戏是例外的卡塔 尔(英语:State of Qatar)射入有个别地点。

图片 1

图1

图第22中学游戏用户选拔生龙活虎颗藕灰珠子,射入图示的职位,于是获得一个图3的范畴。

图片 2

图2

图片 3

图3
当游戏发烧友射入风姿罗曼蒂克颗珠子后,假设射入的珍珠与别的珠子组成了三颗以上接二连三相近颜色的串珠,那一个珠子就能够未有。比如,将黄金年代颗月光蓝珠子射入图4中的地点,就能够爆发三颗颜色相仿的反动珠子。那三颗珠子就能收敛,于是获得图5的规模。

图片 4

图4

图片 5

图5
要求专心的有个别是,图4中的三颗接二连三的肉桂色珠子不会破灭,因为并未珠子射入此中。珠子的一去不返还也许会发生连锁反应。当意气风发串一连相通颜色的珍珠消失后,若无地点左右的珠子颜色同样,何况长度超越2,则能够一而再没有。例如,图6中,射入黄金时代颗土红珠子后,爆发了三颗一连的新民主主义革命珠子。当灰黄珠子消失后,它左右都以反革命的珠子,况兼风姿洒脱共有四颗,于是鲜绿珠子也磨灭了。之后,消失地点的左右都以卡其灰珠子,共有三颗,于是木色珠子也瓦解冰消。最后收获图7的动静。注意,图7中的三颗米白珠子不会瓦解冰消,因为驼灰珠子消失的岗位生机勃勃边是青绿珠子,其他方面是风流珠子,颜色各异。

图片 6

图6

图片 7

图7
除了上述的动静,未有其它的主意能够消去珠子。今后,我们有一排珠子,必要你去破除。对于每生机勃勃轮,你能够自由选用区别颜色的珠子,射入放肆的岗位。你的职务是射出最少的珍珠,将全部珍珠消去。

Input

率先行二个整数n(n ≤
500卡塔尔国,表示珠子的个数第二行n个整数(30个人整数范围内卡塔 尔(英语:State of Qatar),用空格分割,每个整数表示风流浪漫种颜色的珍珠。

Output

多个整数,表示起码必要射出的串珠个数。

Sample Input

9
1 1 2 2 3 3 2 1 1

Sample Output

1

题解:那道题假设不是因为中间的消去,两侧的也会有望不需后生可畏颗就随之消去,固然除去这些规格的话,其实是很好做的,大家设f[i][j]为消除i~j最少要求的珠子个数,枚举叁个k,把区间分为i~k,k+1~j,五个区间,取两个相加中的最小数,还会有意气风发种非常情状便是风流洒脱旦这一个间隔两侧的水彩相通,f[i][j]=min(f[i+1][j-1]+1,f[i][j]),可是加上那些规格,前边的那个式子就有非常大大概形成f[i][j]=min(f[i+1][j-1],f[i][j]);所以大家要用豆蔻年华种奇特的累积方法,把左近的同种颜色的串珠积攒在同个格子里,并记下下邻座的同种颜色的珍珠的个数,那样大家只供给看清间隔两侧的同种颜色珠子的个数相加是不是超过等于3,就足以料定出用第三个照旧第三个姿态。

好了,具体程序注释看。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int now,j,n,a[2000],b[2000],t[2000],f[2000][2000];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    now=1;
    b[now]=a[1];
    t[now]=1;
    for (int i=2;i<=n;i++)
    if (a[i]!=b[now])
    {
        now+=1;
        b[now]=a[i];//这种珠子的颜色
        t[now]=1;//这种珠子的个数(相邻的)
    }
    else t[now]+=1;
    for (int i=1;i<=now;i++)
    for (int j=1;j<=now;j++)
    f[i][j]=2100000000;//无穷大
    for (int i=1;i<=now;i++)
    if (t[i]>1) f[i][i]=1;//消除每种珠子需几颗
    else f[i][i]=2;
    for (int len=2;len<=now;len++)
     for (int i=1;i<=now-len+1;i++)
     {
         j=i+len-1;
         if (b[i]==b[j])//如果说区间两边相同
         {
            if (t[i]+t[j]>=3) f[i][j]=f[i+1][j-1];//如果超过2颗就不需要发射珠子即可消去
            else f[i][j]=f[i+1][j-1]+1;//不然的话就需要一颗珠子
        }

          for (int k=i;k<=j-1;k++)
          f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);//用k把它分成两个区间
     }
    printf("%d\n",f[1][now]);
    return 0;
}

 

相关文章