主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解:P2145 [JSOI2007] 祖玛
最后更新于 2025-08-01 14:02:04
作者
alice_c
分类
题解
题解
P2145
复制 Markdown
查看原文
删除文章
更新内容
## 题意 有一个珠子序列,你可以在任意位置插入任意颜色的珠子。每当连续 $\ge 3$ 个相同颜色的珠子相邻时,它们会消失,并可能引发连锁反应。求至少需要插入几个珠子使所有珠子都被消除。 ## 思路 很显然,这是一道区间 DP 题,我们设 $dp[l][r]$ 表示消除区间 $[l,r]$ 里的珠子需要的最少发射次数。 为了更好的模拟,我们不用关心每个珠子,而是关心颜色段,如果一段珠子被消没了,我们要检查左右颜色段是否颜色相同,可以继续消除。我们可以压缩区间,设 $b_i$ 和 $c_i$,分别统计每个颜色段的颜色和珠子个数。样例 `a: 1 1 2 2 3 3 2 1 1`,压缩区间后就会变成 `b: 1 2 3 2 1` 和 `c: 2 2 2 1 2`。 初始化很明显,如果 $c_i=1$,那么还需要发射两个珠子才能消除;如果 $c_i=2$,还需要发射一个珠子;否则,注意,也需要插入一个珠子。 进行区间 DP,$l$ 是左端点,$r$ 是右端点,如果 $b_l=b_r$ 就可以考虑合并消除,我们把两端和中间 $[l+1,r-1]$ 分开考虑。如果 $c_l+c_r \ge 3$ 就可以直接消除,否则需要再插入一个。枚举中间断点 $k$,主要状态转移方程很板,就是 `dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]`。但是还要考虑三个颜色段颜色相同的情况,即 $b_l=b_k=b_r$($l<k<r$),且 $c_l+c_k<3$ 或 $c_k+c_r<3$,用于排除已经能自动消除的情况发生重复转移。 时间复杂度 $O(cnt^3)$,$cnt$ 表示压缩区间后的颜色段总数。 ## 代码 ```cpp #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,a[505]; int b[505],c[505],cnt=0;//压缩区间,b是颜色,c是个数,cnt是区间总数 int f[505][505];//区间dp,消除l,r中间的珠子需要的发射次数 int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(i>1 && a[i]==a[i-1]) c[cnt]++; else{ b[++cnt]=a[i]; c[cnt]=1; } } memset(f,0x3f,sizeof(f)); for(int i=1;i<=cnt;i++) f[i][i]=(c[i]==1?2:1); for(int i=2;i<=cnt;i++){ for(int l=1;l+i-1<=cnt;l++){ int r=l+i-1; if(b[l]==b[r]){ if(c[l]+c[r]>=3) f[l][r]=min(f[l][r],f[l+1][r-1]); else f[l][r]=min(f[l][r],f[l+1][r-1]+1); } for(int k=l;k<r;k++){ f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]); if(k>l && b[l]==b[k] && b[k]==b[r]) if(c[l]+c[k]<3 || c[k]+c[r]<3) f[l][r]=min(f[l][r],f[l+1][k-1]+f[k+1][r-1]); } } } printf("%d",f[1][cnt]); } ``````
正在渲染内容...
点赞
1
收藏
0