| 题目名称 | 1081. [Tyvj 1966] rainbow与freda染旗 |
|---|---|
| 输入输出 | shimi.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-09-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：24， 通过率：50% | ||||
 Domacles |
100 | 0.006 s | 1.96 MiB | C++ |
 QILIN |
100 | 0.006 s | 1.97 MiB | C++ |
 QhelDIV |
100 | 0.008 s | 1.27 MiB | C++ |
 Truth.Cirno |
100 | 0.016 s | 0.70 MiB | C++ |
 苏轼 |
100 | 0.059 s | 0.31 MiB | C++ |
 Makazeu |
100 | 0.170 s | 9.97 MiB | C++ |
 lingyixiaoyao |
100 | 0.177 s | 9.64 MiB | C++ |
 一個人的雨 |
100 | 0.183 s | 10.71 MiB | C++ |
 svideo |
100 | 0.269 s | 3.30 MiB | C++ |
 HouJikan |
100 | 0.342 s | 10.71 MiB | C++ |
| 关于 rainbow与freda染旗 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
n*m^2的dp能过就行= =没想到模拟怎么做啊
用F[i][j]表示处理好1..i个旗子且第i个旗子颜色为j最少改变的旗子数目 | ||||
|
这题目纯属出题者失误~ 标准算法是DP，可是由于出题者低级失误，模拟都能做过去
Makazeu
2012-10-03 20:37
2楼
| ||||
|
仰慕渣神 模拟 AC！！
本弱菜只想出了一个O(N*M^2)的垃圾DP Makazeu
2012-09-26 20:17
1楼
| ||||
【题目背景】
Freda：aya Rainbow，怎么没看见你城堡挂旗子呀？
Rainbow：我城堡旗子太难看了肿么办T_T
Freda：lala~那好办，我可以帮你染色呀~
Rainbow：嗯嗯，那就试试吧~
【题目描述】
Rainbow城堡的旗子是一个有N个基本单位的长条>_<，每个单位都会被染成前m个大写字母当中的一个颜色。可是，Rainbow认为，两个相邻的单位有相同的颜色很难看的说。所以，Rainbow需要改动一些单位的颜色，使得不存在两个相邻的单位颜色相同。当然了，那些被改动的单位改动之后的颜色也是前m个大写字母当中的一个。Rainbow想请你帮忙计算，它最少要改动多少个单位的颜色才能让旗子好看呢？
【输入格式】
第一行两个整数N、m，表示旗子组成的基本单位数目和颜色的范围。
接下来一行一个长度为N的字符串，字符串的每个字符都是在前m个大写字母的范围内的，表示Rainbow的旗帜。
【输出格式】
一行一个整数表示Rainbow最少改动的单位数目。
【样例输入】
6 3 ABBACC
【样例输出】
2
【提示】
每个测试点1s
样例解释:一种改动方法是ABCACA。当然，还可能有别的改动方法。
对于30%的数据，N<=20.
对于100%的数据，N<=10^5,1<=m<=26.
【来源】
Tyvj 1966