【精品】NOIP经典之祖玛解题报告

【精品】NOIP经典之祖玛解题报告 Zuma解题报告 ZUMA(祖玛问题)解题报告 【SOURCE】2010NOIP连云港模拟 ROUND1第二题 类似题目:POJ2915ZUMA JSOI2007 ZUMA 【DESCRIPTION】 一天陈实来到海州锦屏山玩，在山谷草丛中他发有N(1?N?100)个有颜色的大理石(大理石并不一定“大”)排在一列。他还发现它们有一种特性:当他触摸连续K(2?k?5)个或大于K个的同一色彩的大理石后，它们先是闪烁，再接着是消失了。陈实在家中带了足够多的N个颜色的大理石，他可以将它放在任意的大理石之间(开头与结束也可以放)。 请帮助陈实放入最少的大理石，从而使所有大理石全部消失。 【INPUT】 输入文件zuma.in共两行: 第一行两个整数N与K; 第二行有N个数(每个数都在1到100之间，且有一个空格格开)，这代表陈实发现N个有颜色的大理石。 【OUTPUT】 输出文件zuma.out只有一行; 输出最小放入几个大理石，可以使所有的大理石消失。 【SAMPLE】 【sample1】 zuma.in zuma.out 2 5 3 1 1 【sample2】 zuma.in zuma.out 5 3 2 2 2 3 2 2 【sample】 zuma.in zuma.out 10 4 4 3 3 3 3 2 3 1 1 1 3 【SOLUTION】 经典DP问题zuma，数据范围较小为1~100，对于某区间内的石头进行处理求解，于是想到三位状态表示，可以在1s内出解，但状态的表示的确是本题之关键所在，我们来看下面的: 1、 如何简化数据, 蛋疼之处～连续重复的石头可以合并为一个二元组——c[i]表示颜色，n[i]表示数量 这样就避免了很多重复运算 2 、如何表示状态, 三维状态f[I,j,k]表示需要达成此状态需要的最小石子数 :i、j表示石子i和石子j(以 下的石子都是二元组，不考虑单独的石子)，那么k怎么表示才能使状态无后效性 呢，关键在于祖玛游戏中的一种奖励机制——连消加成，我们从这里得到启示，是 不是可以达成石子j和k个与j颜色相同的石子进行连消呢,当然，我们并不强调k 1 / 3 Zuma解题报告 个石子在序列中的位置，不存在的k可以认为是一种废状态，题目描述中还认为并 不是石子连续超过一定数量就会自动消除，因此不用讨论k+s[j]的范围，这样我们 的工作就大大减轻了。 除此以外，我们可以发现消除的关键并不是将某一段完全消除，而是将某一段消去 形成的状态与其他石子进行组合使得石子数量达到可以消除的石子数量，即可以组 合的石子数，k的加入使得状态没有后效 3、 状态如何转移, 清楚了状态的表示，状态的转移就很容易了，考虑从i到j一段的石子，如果其中 存在与j颜色相同的石子e，那么即可达成状态i->j序列内部的连消，那么首先需要 做的就是消除从e+1到j-1之间石子的没有外部连消的消除(如果有连消的话就会 破坏e和j两块石子)，在进行k块石子与石子j进行连消: F[I,j,k]=min{F[I,e,k+s[j]]+F[e+1,j-1,0]} 另外还应该考虑外部连消的情况，也就是说要将i到j-1的石子以没有与j-1 颜色相 同的石子连消的状态完全删去，那么j石子就要带上k块与之相同颜色的石子进行 消除，rest表示达成连消还需要增加的石子数，此时: F[I,j,k]=min{F[I,j,k],F[I,j-1,0]+rest[s[j]+k]} 【CODE】 program zuma; var f:array[0..101,0..101,0..101] of longint; eliminate c,s,rest:array[0..101] of longint; i,j,k,n,m,ans:longint; function dfs(i,j,k:longint):longint; var tm1,tm2,e:longint; begin if f[i,j,k]<>-1 then exit(f[i,j,k]) else begin tm1:=maxlongint; for e:=i to j-1 do if c[e]=c[j] then begin tm2:=dfs(i,e,s[j]+k)+dfs(e+1,j-1,0); if tm2c[j] then begin inc(j); c[j]:=m; inc(s[j]); end else inc(s[j]); end; n:=j; for i:=0 to k do rest[i]:=k-i; fillchar(f,sizeof(f),$ff); for i:=1 to n do f[i,i-1,0]:=0; ans:=dfs(1,n,0); writeln(ans); close(input); close(output); end. 【GRATITUDE】 减肥童鞋对二元状态的提示 By NEYC SCIENCE DEPARTMENT DrZhang 3 / 3