面试题目，中兴
某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。
特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ;2个花瓶加1朵花是10 ICU不是12 ICU。
编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU因为:
1朵花加2个花瓶: 优惠价:10 ICU
2朵花 正常价: 4 ICU
输入数据
用两个文件表示输入数据。第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFFER．TXT）。 两个文件中都只用整数。
第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。
第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤99），表示共有S种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然， 优惠价要低于该组合中商品正常价之总和。
输出数据
在输出文件OUTPUT．TXT中写 一个数字（占一行）， 该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。
[解决办法]
这道题目是经典的动态规划的题目.因此肯定采用动态规划.
考虑到数据的规模超过了长整型,我们注意在解题过程中采用高精度算法.
规划方程:F[I,J] = MIN { F[I-1,K] + NUM[K+1,J] } (I-1<=K<=J-1)
边界值:F[0,I] := NUM[1,I];
F[I，J]表示前J个数字中添上I个加号后得到的最小值。
NUM[I，J]表示数字串第I位到第J位的数
程序需要的空间约为 20 * 200 * 200.显然难以承受。
但是，还能更优。每一步，我们都只与上一步有关。因此可以采用滚动数组，这样，复杂度就降到了 2 * 200 * 200 左右了。
程序的时间效率约为 20 * 200 * 200.时间上根本不成问题。
这道题目看起来很容易,但是如果在编程时不多加细心，容易的问题也难免会有这样那样的错误。因此,越是简单的题目越要细心，不能粗枝大叶。
三、参考程序
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
program Noi96_4;
const
filein ='input.txt';
fileou ='output.txt';
type
stype =string[202];
var
f1 , f2 :array[1..200] of ^stype;{ 滚动数组 }
st :string;{数字串}
fi, fo :text;
n , m :integer;{字串长度和加号数目}
procedure init;
var
i , j , k : integer;
begin
assign(fi,filein);
assign(fo,fileou);
reset(fi);
rewrite(fo);
readln(fi,st);
n := length(st);
readln(fi,m);
close(fi);
for i := 1 to 200 do
begin new(f1[i]);fillchar(f1[i]^,sizeof(f1[i]^),'0');end;
for i := 1 to 200 do
begin new(f2[i]);fillchar(f1[i]^,sizeof(f1[i]^),'0');end;
for i := 1 to n do
f1[i]^ := copy(st,1,i);
end;
function big(st1,st2:string):boolean;{判断两个字符串的大小}
begin
big := ( length(st1)>length(st2) ) or
( length(st1)=length(st2) ) and ( st1 > st2 );
end;
procedure sum(st1,st2:string;var st3:string);{高精度加法}
var
i , j , k , l , o , p : integer;
begin
st3 := '';
while length(st1)<length(st2) do insert('0',st1,1);
while length(st2)<length(st1) do insert('0',st2,1);
p := 0;
for o := length(st1) downto 1 do
begin
val(st1[o],i,l);
val(st2[o],j,l);
k := (i+j+p) mod 10;
p := (i+j+p) div 10;
st3 := chr(k+48) + st3;
end;
if p>0 then st3 := chr(p+48) + st3;
while (st3[1]='0') and (length(st3)>1) do delete(st3,1,1);
end;
procedure dynamic;{动态规划}
var
i , j , k , l , o , p : integer;
st1 , st2 , st3 : string;
begin
for i := 1 to m do
begin
for j := 1 to 200 do
fillchar(f2[j]^,sizeof(f2[j]^),'0');
for j := i+1 to n-m+i do
for k := i to j-1 do
if (k >= i) and ( k < j ) and (j-k<=101) then
begin
sum(f1[k]^,copy(st,k+1,j-k),st3);
if big(f2[j]^,st3) or (f2[j]^='0') then
f2[j]^ := st3;
end;
for j := 1 to 200 do
f1[j]^ := f2[j]^;
end;
end;
begin
init;
dynamic;
writeln(fo,f1[n]^);
close(fo);
end.
[解决办法]
用dp[i][j][k][l][m]表示第一到第五种商品分别买i,j,k,l,m件的最低价。
首先其中一种价就是无组合的价。
然后用组合价来更新。比如i1,j1,k1,l1,m1的价是x
dp[i][j][k][l][m] + x可以来更新dp[i+i1][j+j1][k+k1][l+l1][m+m1]
注意到不超5.可以更新状态表示为
用dp[m+l*10+k*100+j*1000+i*10000]表示dp[i][j][k][l][m]
