最佳覆盖问题是经典的线形规划类型，通常是给定一排任务（或物品），你需要将其分为Ｋ个部分，通常Ｋ＜＝Ｎ，分出部分时通常有一定的花费，你需要让总费用最大或最小

其一般动态模型为

Ｆ［Ｉ，Ｊ］＝ＭＩＮ（　Ｆ［Ｉ－１，Ｋ－１］+ＳＵＭ［Ｉ，Ｊ］　）

初值Ｆ［Ｉ，Ｊ］＝∞　Ｆ［０，０］＝０　ＳＵＭ［Ｉ，Ｊ］是把物品Ｉ到Ｊ分在一起的花费，它通常的时间复杂度是（Ｋ*Ｎ＾２）的

例题：

给定k个大小不同的灌木丛，它们因为霜冻需要保护。假定这些灌木丛按照大小排序，即灌木丛0是最小的，灌木丛k-1是最大的。这里把为灌木丛i制作覆盖层的花费记作ci。但是由于制造技术上的局限，最多只能制造n种不同大小的保护层，这里n＜＝k。较大的覆盖层能够保护较小的灌木丛。我们的目标是决策n个保护层的大小，使之能以最小的花费覆盖所有的灌木丛。

我们来看这样一个例子：有k = 10个灌木丛，每种大小的覆盖层的花费
为(c0; :::; c9) = 1; 4; 5; 7; 8; 12; 13; 18; 19; 21),且由于技术局限，只能制作n = 3种
大小的覆盖层。那么最佳的方案就是依次制造出大小为9,6,4的覆盖层(即使用大
小为9的覆盖层保护灌木丛9,8,7，用大小为6的覆盖层保护灌木丛6和5，用大小
为4的覆盖层保护灌木丛0至灌木丛4)，其总花费f(3; 9) = 129

program cov;
var c:array[0..10] of longint;
    f:array[0..3,0..10] of longint;
    i,j,k:longint;
begin
for i:=1 to 10 do read(c[i]);
fillchar(f,sizeof(f),$7f);
f[0,0]:=0;
for i:=1 to 3 do
for j:=i to 10 do
for k:=i to j do
if not((i=1)and(k<>1)) then
if f[i-1,k-1]+(j-k+1)*c[j]<f[i,j] then
f[i,j]:=f[i-1,k-1]+(j-k+1)*c[j];
writeln(f[3,10]) ;
end.