【动归】rainbow与freda染旗

51 阅读 0 评论 34 点赞

我是靠谱客的博主悦耳中心，最近开发中收集的这篇文章主要介绍【动归】rainbow与freda染旗，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

rainbow与freda染旗

From This_poet

背景 Background

Freda：aya Rainbow，怎么没看见你城堡挂旗子呀？
Rainbow：我城堡旗子太难看了肿么办T_T
Freda：lala~那好办，我可以帮你染色呀~
Rainbow：嗯嗯，那就试试吧~

描述 Description

Rainbow城堡的旗子是一个有N个基本单位的长条>_<，每个单位都会被染成前m个大写字母当中的一个颜色。可是，Rainbow认为，两个相邻的单位有相同的颜色很难看的说。所以，Rainbow需要改动一些单位的颜色，使得不存在两个相邻的单位颜色相同。当然了，那些被改动的单位改动之后的颜色也是前m个大写字母当中的一个。Rainbow想请你帮忙计算，它最少要改动多少个单位的颜色才能让旗子好看呢？

输入格式 InputFormat

第一行两个整数N、m，表示旗子组成的基本单位数目和颜色的范围。
接下来一行一个长度为N的字符串，字符串的每个字符都是在前m个大写字母的范围内的，表示Rainbow的旗帜。

输出格式 OutputFormat

一行一个整数表示Rainbow最少改动的单位数目。

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

样例解释:一种改动方法是ABCACA。当然，还可能有别的改动方法。
对于30%的数据，N<=20.
对于100%的数据，N<=10^5,1<=m<=26.

时间限制 TimeLimitation

每个测试点1s

第一次自己做出来一道dp题，虽然很简单。。。虽然还可以用贪心写。。。。。

暴力dp f[i,j]表示 1..i面旗子，第i面旗子染成颜色j的最小染色方案。

显然第i面旗子的方案由第i-1面旗子的方案转移而来

对于第i面旗子有两种决策，不染色，或染成颜色j。

1：第i-1面旗子染成颜色 j1 且 j1<>a[i]

f[i,a[i]]:=min(f[i,a[i]],f[i-1,j1])

2: 第i-1面旗子染成j1色，第i面旗子染成j色，且(j<>j1)( j<>a[i])

f[i,j]:=min(f[i,j],f[i-1,j1])+1

最后输出f[n,i]里面最小的值 1<=i<=m

var n,m,i,j,j1,ans:longint;
a:array[1..100000]of longint;
f:array[0..100000,1..26]of longint;
x:char;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
begin
readln(n,m);
for i:=1 to n do
begin
read(x);
a[i]:=ord(x)-64;
end;
fillchar(f,sizeof(f),$7f);
for i:=1 to m do f[0,i]:=0;
f[1,a[1]]:=0;
for i:=1 to n do
begin
for j1:=1 to m do
//i-1
begin
if j1<>a[i] then f[i,a[i]]:=min(f[i,a[i]],f[i-1,j1]);
for j:=1 to m do if j<>a[i] then //change
if j<>j1 then f[i,j]:=min(f[i,j],f[i-1,j1]+1)
end;
end;
ans:=maxlongint;
for i:=1 to m do ans:=min(ans,f[n,i]);
writeln(ans);
readln;readln;
end.