Kitty猫基因突变解题报告

题意简述

　　输入一个长为（k≤7）01串s，要求将其中w（w≤30）个0变化为1，使得变化后的串s'的"ABC编码"长度T+变化的成本C(s , s')最小，其中，ABC编码规则是：
　　　

　　而成本C(s , s')就是发生变化的那些字符0的变化成本的总和（给定所有字符的变化成本）。约束条件：k≤7，w≤30且s串中一定有w个0，每一个字符的变化成本且为整数。

算法分析

　　首先，我们分析一下ABC编码的规则：由于若s串并非全是0或1时，规则将s分成两个等长的子串分别处理，两个子串之间没有任何联系，原串对子串也没有影响，因此本题符合无后效性原理。而将某一个串s中的w个0变化成1的最优解F(s,w)一定是将s1中的k（0≤k≤w，且s1中有k个0，s2中有(w-k)个0）个0变化成1，并将s2中的(w-k)个0变化成1，并将两个子问题分别取最优解相加。因此，本题又符合最优子结构原理，可以使用动态规划。动态规划的方程如下：


程序

{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65520,0,655360}
Const
　　InFile = 'AH02T8.in'; 　　　　//输入文件
　　OutFile = 'AH02T8.out'; 　　　//输出文件
　　Limit = 200; 　　　　　　　　//最大长度128放宽至200,最大变化数30放宽至200

Type
　　Tmem1 = array[0..Limit] of longint; //状态值若为0，则是"不可用"或未改进
　　Tmem = array[0..1 , 1..Limit] of ^Tmem1; 　　//循环数组存储状态
　　　　　　　　　//含义：mem[阶段(循环数组) , 第几个子串]^[0的变化个数]
　　Tdata = array[1..Limit] of integer; 　　　　　//原串类型
　　Tcost = array[1..Limit] of longint; 　　　　　//变化花费类型

Var
　　mem : Tmem; 　　　　　　　　//动态规划的状态记录
　　data : Tdata; 　　　　　　　//原01串
　　cost : Tcost; 　　　　　　　//花费
　　K , W ,
　　now , N : longint; 　　　　//now: 循环数组的指针

procedure init;　　　　　　　　　　　　　　　　　　//输入
var
　　i : integer;
　　c : char;
begin
　　assign(INPUT , InFile); ReSet(INPUT); 　　　　//打开输入文件
　　　readln(K , W);
　　　N := 1 shl K; 　　　　　　　　　　　　　　　　//将N转化成01串的长度
　　　for i := 1 to N do 　　　　　　　　　　　　　//读入01串
　　　　begin
　　　　　　read(c);
　　　　　　data[i] := ord(C) - ord('0'); 　　　　//将字符转化成数值
　　　　end;
　　　for i := 1 to N do
　　　　read(cost[i]); 　　　　　　　　　　　　　　//读入花费
　　Close(INPUT);　　　　　　　　　　　　　　　　　//关闭文件
end;　　　　　　　　　　　　　　　　　　　　　　　　//of init

procedure work; 　　　　　　　　　　　　　　　　　　//处理过程
var
　　i , tmp ,
　　j , sum ,
　　t ,
　　start ,
　　stop ,
　　target ,
　　count ,
　　tmpsum ,
　　same : longint;
begin
　　now := 0;　　　　　　　　　　　　　　　　　　//循环数组指针归0
　　for i := 1 to N do
　　　begin
　　　　new(mem[0 , i]); fillchar(mem[0 , i]^ , sizeof(mem[0 , i]^) , 0);
　　　　new(mem[1 , i]); fillchar(mem[1 , i]^ , sizeof(mem[1 , i]^) , 0);
　　　end; 　　　　　　　　　　　　　　　　　　　　//初始化动态数组
　　for i := 1 to N do
　　　begin
　　　　　mem[now , i]^[0] := 1;
　　　　　if data[i] = 0 then
　　　　　　mem[now , i]^[1] := cost[i] + 1;
　　　end; //动态规划的边界条件
　　N := N div 2; tmp := 2; 　　　　　　　　　　//01子串个数初始化
　　　　　　　　　　　　　　　　　　　　　　　　　//每一个子串长度初始化
　　for i := K downto 1 do 　　　　　　　　　　　//循环阶段
　　　begin
　　　　now := 1 - now;　　　　　　　　　　　　//改变循环数组指针
　　　　for j := 1 to N do 　　　　　　　　　　//循环01子串
　　　　　begin
　　　　　　fillchar(mem[now , j]^ , sizeof(mem[now , j]^) , 0);　//初始化
　　　　　　start := (j - 1) * tmp + 1; stop := j * tmp; 　　//子串的位置
　　　　　　sum := 0;
　　　　　　for t := start to stop do
　　　　　　　if data[t] = 0 then
　　　　　　　　inc(sum); 　　　　　　　　　　　　　　　　　//查找0的个数
　　　　　　if sum < W then
　　　　　　　target := sum
　　　　　　else
　　　　　　　target := W; 　　　　　　　　　　　　　　　　　//最多的突变个数
　　　　　　same := 1;
　　　　　　for t := start + 1 to stop do
　　　　　　　if data[t] <> data[start] then
　　　　　　　　begin
　　　　　　　　　same := 0;
　　　　　　　　　break;
　　　　　　　　end;
　　　　　　if same = 1 then //如果子串全部都为0或1
　　　　　　　mem[now , j]^[0] := 1 //0个变化的最小值为1
　　　　　　else
　　　　　　　mem[now , j]^[0] := mem[1 - now , j * 2 - 1]^[0] + mem[1 - now , j * 2]^[0] + 1; 　　　　　　//否则是s1串0变化最小值+s2串0变化最小值+1

　　　　　　for t := 1 to target do 　　　　　　　　//循环变化数目
　　　　　　　if t = sum then 　　　　　　　　　　　//如果全部0都变成了1
　　　　　　　　begin
　　　　　　　　　tmpsum := 1;
　　　　　　　　　for count := start to stop do
　　　　　　　　　　if data[count] = 0 then
　　　　　　　　　　　inc(tmpsum , cost[count]); 　　　　　//计算总代价数
　　　　　　　if (mem[now , j]^[t] = 0) or (tmpsum < mem[now , j]^[t]) then
　　　　　　　　mem[now , j]^[t] := tmpsum; 　　　　　　　//赋值
　　　　　　end
　　　　　else
　　　　　　for count := 0 to t do　　　　　　　　　　//循环s1串的变化个数
　　　　　　　if (mem[1 - now , j * 2 - 1]^[count] <> 0) and (mem[1 - now , j * 2]^[t - count] <> 0) then　//如果变化个数满足条件(k≤zero1,w-k≤zero2)
　　　　　　　　begin
　　　　　　　　　tmpsum := mem[1 - now , j * 2 - 1]^[count] + mem[1 - now , j * 2]^[t - count] + 1;　　　　　　　　　　　　//计算代价
　　　　　　　　　if (mem[now , j]^[t] = 0) or (mem[now , j]^[t] > tmpsum) then 　　　　　　　　　　　　　　　　　　　　　　//如果可以改进
　　　　　　　　　　mem[now , j]^[t] := tmpsum; //赋值
　　　　　　　　end;
　　　　　N := N div 2; tmp := tmp * 2; 　//01子串个数减半，每一个子串长度*2
　　　end;
end; //of work

procedure out; 　　　　　　　//输出过程
begin
　　assign(OUTPUT , OutFile); ReWrite(OUTPUT);　　　　　　//打开输出文件
　　　writeln(mem[now , 1]^[W]);　　　　　　　　　　　　　//输出答案
　　Close(OUTPUT); 　　　　　　　　　　　　　　　　　　　　//关闭输出文件
end; //of out

Begin
　　init;
　　work;
　　out;
End. //of main