BZOJ1032-[JSOI2007]祖码Zuma

2024-02-15 06:10
文章标签 jsoi2007 祖码 zuma bzoj1032

本文主要是介绍BZOJ1032-[JSOI2007]祖码Zuma,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最近突然发现自己dp不太行,就回来补几道经典(水)题,强化dp。

1032: [JSOI2007]祖码Zuma

Time Limit: 10 Sec   Memory Limit: 162 MB
Submit: 1222   Solved: 639
[ Submit][ Status][ Discuss]

Description

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

图1

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

图2

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

图4

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

图6

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

Input

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

Output

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

Sample Input

9
1 1 2 2 3 3 2 1 1

Sample Output

1

        这是一道非常明显的区间dp,先求出每一段相同颜色的区间,然后用dp[i][j]表示从i到j的最少需要珠子个数。枚举区间[i,j]以及断点k,dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])。特别注意当i的颜色与j相同时,当(l[i]==r[i]&&l[j]==r[j])即左右各有一颗珠子时,f[i][j]=min(f[i][j],f[i+1][j-1]+1);因为需要在中间消去后再打入一颗。否则f[i][j]=min(f[i][j],f[i+1][j-1]);直接消去。

Code:

#include<bits/stdc++.h>
#define N 505
using namespace std;
int cnt=0,color[N],f[N][N],l[N],r[N];
inline int read()
{int f=1,x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f;return x;
}
int main()
{int n=read();color[0]=-1;for(int i=1;i<=n;i++){int x=read();if(x!=color[cnt]){color[++cnt]=x;r[cnt-1]=i-1;l[cnt]=i;}}memset(f,0x3f,sizeof(f));r[cnt]=n;for(int i=1;i<=cnt;i++)if(l[i]==r[i])f[i][i]=2;else f[i][i]=1;for(int len=2;len<=cnt;len++)for(int i=1;i<=cnt-len+1;i++){int j=i+len-1;for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);if(color[i]==color[j])	{if(l[i]==r[i]&&l[j]==r[j])f[i][j]=min(f[i][j],f[i+1][j-1]+1);elsef[i][j]=min(f[i][j],f[i+1][j-1]);}}printf("%d\n",f[1][cnt]);return 0;
}

这篇关于BZOJ1032-[JSOI2007]祖码Zuma的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/710612

相关文章

bzoj 1031 [JSOI2007]字符加密Cipher(后缀数组)

1031: [JSOI2007]字符加密Cipher Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 8411  Solved: 3742 [Submit][Status][Discuss] Description   喜欢钻研问题的JS同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法 :把需要加密的信息排成

bzoj1030: [JSOI2007]文本生成器

传送门:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1030 思路:直接算好像比较困难,所以考虑先算不可读的串的个数,再拿总串数去减。 不可读的串的数量就是在AC自动机上走M步而不经过结尾节点(包括结尾点和fail指向结尾点的节点)的路径条数。 这个怎么求呢? 设f[i][j]表示走i步,现在在j号节点的路径条数。 那么f[i]

[BZOJ1032][P1840] 祖玛 记忆化搜索 动态规划

描述 Description  某天,小x在玩一个经典小游戏——zumo。zumo游戏的规则是,给你一段长度为n的连续的彩色珠子,珠子的颜色不一定完全相同,但是,如果连续相同颜色的珠子大于等于k个,这些珠子就会消失。当然,最初的状态可能不必要直接消掉一些珠子(见样例)。现在你有无穷个所有颜色的珠子,并且你可以在任意地方插入珠子。现在提出问题:给你一个固定的状态,你最少需要用多少个小球,

【区间dp】Codeforces Round 336 (Div 2) D Zuma

Codeforces Round 336 (Div 2) D Zuma 题意:给一个长度为n的字符串,每次可以删掉其中的一个回文子串,问你最少需要删多少次 思路:拿到的时候我愣了一下,没想到是区间dp,emm,事实上它和经典区间dp括号匹配是一样的思路 dp[i][j]代表i~j删完需要的次数,if(c[i]==c[j]) dp[i][j]=dp[i+1][j-1] (可以和i+1~j-

P2145 [JSOI2007] 祖码

[JSOI2007] 祖码 - 洛谷https://www.luogu.com.cn/problem/P2145很经典的一道区间dp,区间dp的部分都挺好想的: 我们用数组f [ i ][ j ]表示消除区间[ i , j ]需要的竹子的个数.那么我们进行区间dp,从小区间合并到大区间,状态转移方程式(这里就是板子)就是 f [ i ][ j ]=min(f [ i ][ j ],f [ i

[JSOI2007]祖码Zuma/[bzoj]1032

1032: [JSOI2007]祖码Zuma Time Limit: 10 Sec   Memory Limit: 162 MB Submit: 633   Solved: 315 [ Submit][ Status][ Discuss] Description 这是一个流行在Jsoi的游戏,名称为祖玛。精致细腻的背景,外加神秘的印加音乐衬托,彷佛置身在古老的国度里面,进行一个

bzoj1030 [JSOI2007]文本生成器

传送门 Description   JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说,生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章a包含单词b,当

BZOJ 1027 [JSOI2007]合金

Description   某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的 原材料中铁铝锡的比重不同。然后,将每种原材料取出一定量,经过融解、混合,得到新的合金。新的合金的铁铝 锡比重为用户所需要的比重。 现在,用户给出了n种他们需要的合金,以及每种合金中铁铝锡的比重。公司希望能 够订购最少种类的原材料,并且使用这些原材料可以加工出用户需要的所