小明的礼物
题目描述
小明参加当地的程序设计竞赛，赢得了两张当地两张超市优惠卷，面值分别为A元和B元。使用优惠卷时，不能取出现金，也不能两张余额合并使用。
他想给妈妈准备多份生日礼物，共N个。根据对妈妈的了解，小明对礼物进行了分类。有些是必须买的，若不买，妈妈生日就会不开心；有些可买，可不买。
接着小明又做了研究，查询得到每个礼物在超市的价格，以及妈妈收到这份礼物后的开心值。
于是小明出发给妈妈买生日礼物。刚走到超市门口，就发现，今天恰逢店庆，只要生日和店庆日相同，就可以免费获得一份礼物。
现在，有了一个免费机会，以及两张优惠券，问小明可以买到的礼物，使得妈妈最大的开心值为多少。
输入
第一行三个整数A，B和N(1<=A<=500,1<=B<=50,1<=N<=300)，分别表示两张优惠券的面值和小明想要买的礼物数。
接下来N行，每行三个整数P，H和S（1<=P,H<=1000,S=0或者1），表示该礼物的信息。P表示该物品的价格，H表示妈妈收到这个礼物的高兴值，S＝1表示这个物品必须买，若没有买，妈妈就会不高兴；若S＝0，表示这个物品可以买，也可以不买。
输出
输出妈妈的最大高兴值，若有其中任意一个必买的礼物没有买，妈妈就会不高兴直接输出-1.
样例输入
3 2 4 3 10 1 2 10 0 5 100 0 5 80 0
样例输出
120
提示
【样例解释1】用A优惠券买礼物1，B优惠券买礼物2，免费机会买礼物3
样例2：
3 2 4
3 10 1
2 10 0
5 100 0
5 80 1
100
用A优惠券买礼物1，B优惠券买礼物2，免费机会买礼物4
【数据范围】
20%的数据n<=25
来源
析：这道题是动态规划中的精英难题，不难看出这是一题背包题，我也承认，这是。但是普通的背包根本枚举不了所有的情况，这题需要有非常强大的思维能力，细细品味一下，其实也并不难，只需要分点分治，把一种背包解决不了的问题分开用别的背包解，再对背包数组加维就可以轻松解题。
var
n,m,i,j,s,p,h,k,x,y,l:longint;
f:array[0..300,0..500,0..50,0..1] of longint;
//【分别是礼物总数、两张优惠券和是否要使用免费机会】的最大开心值
ans:int64;
function max(x,y:longint):longint;
begin
if x>y then
exit(x);
exit(y);
end;
begin
readln(x,y,n);
for i:=0 to n do
for j:=0 to x do
for k:=0 to y do
for l:=0 to 1 do
f[i,j,k,l]:=-maxlongint-1;
f[0,0,0,0]:=0;
for i:=1 to n do
begin
readln(p,h,s);
for j:=0 to x do
for k:=0 to y do//枚举优惠券面值
if s=1 then//一定要买的礼物
begin
f[i,j,k,1]:=f[i-1,j,k,0]+h;//上一个的最大开心值+当前的开心值（当前用免费机会）
if j>=p then//第一张优惠券比价格大
begin
f[i,j,k,0]:=f[i-1,j-p,k,0]+h;//不用免费机会但用优惠劵的情况
f[i,j,k,1]:=max(f[i,j,k,1],f[i-1,j-p,k,1]+h);//都用免费机会
end;
if k>=p then//同上
begin
f[i,j,k,0]:=max(f[i-1,j,k-p,0]+h,f[i,j,k,0]);
f[i,j,k,1]:=max(f[i,j,k,1],f[i-1,j,k-p,1]+h);
end;
end else//当前礼物可有可无，方法同上
begin
f[i,j,k,0]:=f[i-1,j,k,0];
f[i,j,k,1]:=max(f[i-1,j,k,0]+h,f[i-1,j,k,1]);
if j>=p then
begin
f[i,j,k,0]:=max(f[i-1,j-p,k,0]+h,f[i,j,k,0]);
f[i,j,k,1]:=max(f[i,j,k,1],f[i-1,j-p,k,1]+h);
end;
if k>=p then
begin
f[i,j,k,0]:=max(f[i-1,j,k-p,0]+h,f[i,j,k,0]);
f[i,j,k,1]:=max(f[i,j,k,1],f[i-1,j,k-p,1]+h);
end;
end;
end;
ans:=-maxlongint-1;
for i:=0 to x do
for j:=0 to y do
if ans<max(f[n,i,j,0],f[n,i,j,1]) then
ans:=max(f[n,i,j,0],f[n,i,j,1]);//找最大
if ans<0 then
writeln(-1) else//办不到
writeln(ans);
End.
小明的喷漆计划
题目描述
小明极其喜欢涂鸦，总是在墙上涂上各种颜色的漆。现在小明得到一个任务，需要喷涂一段空白围墙，且单位长度内的颜色都是相同的。小明有一种喷涂工具，它可以给任意长度的一段墙面涂上任意颜色的漆，这样的操作计为一次操作。小明要完成这个任务，又想使得操作次数尽量少，就请你帮他解决这个问题吧。
输入
有多组输入数据。
每组包含一个长度不超过100的字符串（均由小写字母组成），代表需要涂鸦的墙面目标状态
输出
至少需要几次操作，可达到目标
样例输入
aaaaaa
Fedcbaabcdef
Aaabbbbb
aaabbbaaa
样例输出
1
6
2
2
提示
析：这道题很容易让人想到栈，但是栈要维护单调性，在字符串上做不到，只能催生出动态规划这一杀手锏。动态规划这题可谓是神出鬼没，不仔细看，就会写成单调栈（做不到，0分）动态规划的方程非常简单
Min(f[i,j],f[i,k]+f[k+1,j]);
If s[i]=s[j] dec(f[i,j]);
i是起点，k是中继，J是目标
STD：
var
n,m,i,j,k,len:longint;
f:array[0..200,0..200] of longint;
s:string;
function min(a,b:longint):longint;
begin
if a<b then
exit(a);
exit(b);
end;
begin
while not eof do
begin
readln(s);
n:=length(s);
for i:=0 to 200 do
for j:=0 to 200 do
f[i,j]:=maxlongint;
for i:=1 to n do
f[i,i]:=1;
for len:=2 to n do//N个数有n-1个空隙，从2开始
for i:=1 to n-len+1 do//当前的区间长度
begin
j:=i+len-1;//区间末尾
for k:=i to j-1 do//枚举区间
f[i,j]:=min(f[i,j],f[i,k]+f[k+1,j]);
if s[i]=s[j] then f[i,j]:=f[i,j]-1;//多出来的一下去掉
end;
writeln(f[1,n]);
end;
end.