洛谷 P2145 [JSOI2007]祖码 题解【DP】【区间DP】

作者: wjyyy 分类: DP,区间DP,解题报告 发布时间: 2018-06-17 16:06

点击量:20

 

   一个比较有技巧的区间DP题,要缩点,将相同颜色的点整理到一起。

 

题目描述

这是一个流行在Jsoi的游戏,名称为祖玛。精致细腻的背景,外加神秘的印加音乐衬托,彷佛置身在古老的国度里面,进行一个神秘的游戏——这就是著名的祖玛游戏。祖玛游戏的主角是一只石青蛙,石青蛙会吐出各种颜色的珠子,珠子造型美丽,并且有着神秘的色彩,环绕着石青蛙的是载着珠子的轨道,各种颜色的珠子会沿着轨道往前滑动,石青蛙必需遏止珠子们滚进去轨道终点的洞里头,如何减少珠子呢?就得要靠石青蛙吐出的珠子与轨道上的珠子相结合,颜色相同者即可以消失得分!直到轨道上的珠子通通都被清干净为止。 或许你并不了解祖玛游戏。没关系。这里我们介绍一个简单版本的祖玛游戏规则。一条通道中有一些玻璃珠,每个珠子有各自的颜色,如图1所示。玩家可以做的是选择一种颜色的珠子(注意:颜色可以任选,这与真实游戏是不同的)射入某个位置。

 

 

图2中玩家选择一颗蓝色珠子,射入图示的位置,于是得到一个图3的局面。

 

图3

 

当玩家射入一颗珠子后,如果射入的珠子与其他珠子组成了三颗以上连续相同颜色的珠子,这些珠子就会消失。例如,将一颗白色珠子射入图4中的位置,就会产生三颗颜色相同的白色珠子。这三颗珠子就会消失,于是得到图5的局面。

 

需要注意的一点是,图4中的三颗连续的黄色珠子不会消失,因为并没有珠子射入其中。珠子的消失还会产生连锁反应。当一串连续相同颜色的珠子消失后,如果消失位置左右的珠子颜色相同,并且长度大于2,则可以继续消失。例如,图6中,射入一颗红色珠子后,产生了三颗连续的红色珠子。当红色珠子消失后,它左右都是白色的珠子,并且一共有四颗,于是白色珠子也消失了。之后,消失位置的左右都是蓝色珠子,共有三颗,于是蓝色珠子也消失。最终得到图7的状态。注意,图7中的三颗黄色珠子不会消失,因为蓝色珠子消失的位置一边是紫色珠子,另一边是黄色珠子,颜色不同。

 

图7 除了上述的情况,没有其他的方法可以消去珠子。现在,我们有一排珠子,需要你去消除。对于每一轮,你可以自由选择不同颜色的珠子,射入任意的位置。你的任务是射出最少的珠子,将全部珠子消去。

输入输出格式

输入格式:

第一行一个整数n(n ≤ 500),表示珠子的个数 第二行n个整数(32位整数范围内),用空格分割,每个整数表示一种颜色的珠子。

输出格式:

一个整数,表示最少需要射出的珠子个数。

输入输出样例

输入样例#1:
9
1 1 2 2 3 3 2 1 1
输出样例#1:
1

说明

据说此题标程有误,致使数据全错….

 

   这种题目要么是贪心,要么是DP,不过DP就应该是区间DP,还要加一点技巧以及打表

 

   首先我们要对题目中的点“缩点”,将初始相邻的同色龙珠变成一个点,如果这个合并后的龙珠只有单独一个,那么它还需要2个同色龙珠才能消掉,如果达到两个或更多,那么它只需要一个就可以消除。这样我们就有了\(f[i][i]=\left\{\begin{aligned} \ 1,num[i]\ge 2 \\ \ 2,num[i]=1 \\\end{aligned}\right.\)由于缩点后相邻龙珠不同色,不能合并,那么根据这个特点我们有了一个状态转移方程:f[i][j]=f[i][k]+f[k+1][j],其中k是断点,是区间DP的标志。

 

   但仅仅这样是不够的,我们的龙珠在碰撞时,如果积累超过2个是会继续消除的。那么我们对原来的区间进行扩展,如果一个区间的两边颜色相同,并且个数加起来超过2个,就可以直接合并;如果只有两个,那么就需要另一个颜色相同的龙珠来消掉,我们选择打掉它。(这样就不再找第三个消除,第三个就要多付出一个代价,也就时是标程DP错误的原因,但尽管这样我们学习的是DP而不是杠

 

   那么当\(c[i]==c[j]\)时,有一个状态转移方程,\(f[i][j]=max(f[i][j],\left\{\begin{aligned} \ f[i+1][j-1]+1,num[i]+num[j]=1 \\ \ f[i+1][j-1],num[i]+num[j]\ge 2 \\\end{aligned}\right.\),同样要注意j-i!=1这个边界。

 

某谷上一个可能是标程的程序

 

Code:

#include<cstdio>
#include<cstring>
int min(int x,int y)
{
    return x<y?x:y;
}
struct node
{
    int c,num;
}t[555];
int f[555][555];
int main()
{
    memset(f,0x3f,sizeof(f));//初始化
    int n,cnt=0,u;
    scanf("%d",&n);
    scanf("%d",&u);
    t[++cnt].c=u;
    t[cnt].num=1;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&u);
        if(u==t[cnt].c)
            t[cnt].num++;
        else
        {
            t[++cnt].c=u;
            t[cnt].num=1;
        }
    }
    for(int i=1;i<=cnt;i++)
        if(t[i].num>1)//初始化
            f[i][i]=1;
        else
            f[i][i]=2;
    for(int l=1;l<cnt;l++)
        for(int i=1;i<=n-l;i++)
        {
            for(int k=i;k<=i+l;k++)
                f[i][i+l]=min(f[i][i+l],f[i][k]+f[k+1][i+l]);//区间DP
            if(t[i].c==t[i+l].c&&l>1)
            {
                if(t[i].num+t[i+l].num>=3)
                    f[i][i+l]=min(f[i][i+l],f[i+1][i+l-1]);//扩展性
                else
                    f[i][i+l]=min(f[i][i+l],f[i+1][i+l-1]+1);
            }
        }
    printf("%d\n",f[1][cnt]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */