動態規劃算法的應用
壹.動態規劃的概念
近年來，涉及動態規劃的競賽問題越來越多，NOI每年幾乎至少有壹個問題需要用動態規劃來解決。但是比賽要求越來越多的選手使用動態編程知識，不再局限於簡單的遞歸和建模。
要理解動態規劃的概念，首先要知道什麽是多階段決策問題。
1.多階段決策問題
如果壹種活動過程可以分為幾個相互關聯的階段，每個階段都需要做出決策(措施)，而壹個階段的決策確定後，往往會影響下壹個階段的決策，從而完全確定壹個過程的活動路線，則稱為多階段決策問題。
每個階段的決策構成了壹個決策序列，這個序列被稱為策略。每個階段都有幾個決策可供選擇，所以有很多策略可供我們選擇。對應壹個策略，可以確定活動的效果，這個效果可以用數量來確定。不同的策略有不同的效果。多階段決策問題是在可選擇的策略中選擇壹個最優策略，以達到預定標準下的最佳效果。
2.動態規劃問題中的術語
階段:把給定的解題過程分成幾個相互關聯的階段，以便於解題。對於不同的過程，階段的數量可以不同。描述階段的變量稱為階段變量。在大多數情況下，階段變量是離散的，用k表示。另外，也有階段變量是連續的情況。如果壹個過程可以在任何時候作出決定，並且在任何兩個不同的時間之間允許無限數量的決定，則階段變量是連續的。
在前面的例子中，第壹階段是A點，而第二階段是從A點到B點，第三階段是從B點到C點，第四階段是從C點到d點。
狀態:狀態表示每個階段開始面臨的自然或客觀條件，不以人的主觀意誌為轉移，也稱不可控因素。在上面的例子中，狀態是某個階段的開始位置，它不僅是該階段壹條道路的起點，也是前壹階段壹條分支的終點。
在前面的示例中，第壹級具有壹個狀態，即A，而第二級具有兩個狀態B1和B2，第三級具有三個狀態C1、C2和C3，第四級是狀態D..
過程的狀態通常可以用壹個或壹組數字來描述，這些數字稱為狀態變量。壹般來說，狀態是離散的，但有時為了方便起見，把它看作是連續的。當然，在現實生活中，由於變量形式的限制，所有的狀態都是離散的，但從分析的角度來看，有時將狀態視為連續會大有裨益。另外，狀態可以有多個分量(多維情況)，所以用向量表示；此外，每個階段中的狀態維度可以不同。
當過程以所有可能的不同方式發展時，過程每壹段的狀態變量將在壹定範圍內取值。狀態變量的值的集合稱為狀態集。
無後效:我們要求狀態具有以下性質:如果給定了某壹階段的狀態，則該階段後過程的發展不受前幾個階段狀態的影響，當所有階段確定後，整個過程就確定了。換句話說，流程的每個實現都可以用壹個狀態序列來表示。在前面的示例中，每個階段的狀態是線條的起點。如果這些點的順序確定了，那麽整條線就完全確定了。從某壹階段後的線開始，給定該段起點時，不受前壹條線(通過點)的影響。狀態的這種屬性意味著壹個過程的歷史只能通過當前狀態影響其未來的發展，這叫做無後效。
決策:給定壹個階段的狀態後，從該狀態演化到下壹個階段的選擇(行動)稱為決策。在最優控制中，也叫控制。在許多問題中，決策可以自然地表示為壹個數字或壹組數字。不同的決策對應不同的價值觀。描述決策的變量稱為決策變量。因為狀態不滿足後效，所以在每個階段選擇決策時只需要考慮當前狀態，而不需要考慮過程的歷史。
決策變量的範圍稱為允許決策集。
策略:每個階段的壹系列決策被稱為策略。對於每壹個實際的多階段決策過程，可用策略都有壹定的範圍限制，稱為允許策略集。在策略集中允許最佳效果的策略稱為最優策略。
給定K階段的狀態變量x(k)的值，如果確定了該階段的決策變量，則完全確定了k+1階段的狀態變量x(k+1)，即x(k+1)的值隨x(k)的值和K階段的決策u(k)而變化。這就是從K階段到k+1階段的狀態轉移規律，稱為狀態轉移方程。
最優性原則:作為整個過程的最優策略，它滿足剩余的子策略相對於前壹個決策形成的狀態必須構成“最優子策略”。
最優性原理其實就是需求問題最優策略的子策略，也是最優的。讓我們通過重新分析前面的例子來說明這壹點:從A到D，我們知道最短路徑是A？B1？C2？d、這些點的選擇構成了本例的最優策略。根據最優性原理，這個策略的每個子策略都應該是最優的:A？B1？C2到C2的最短路徑是B1？C2？D也是從B1到D的最短路徑...——正是如此，所以我們認為這個例子符合最優性原則的要求。
[編輯本段]動態規劃練習
USACO
2.2子集和
題目如下:
對於從1到n的連續整數集，可以分成兩個子集，保證每個集合的數字和相等。
例如，如果N=3，{1，2，3}可以分成兩個子集，每個子集的所有數之和相等:
{ 3 }和{1，2}
這是唯壹的分布(交換集位置被認為是相同的分區方案，因此不會增加分區方案的總數)。
如果N=7，集合{1，2，3，4，5，6，7}有四種劃分方式，每個分布子集的個數之和相等:
{1，6，7}和{2，3，4，5 } {註1+6+7=2+3+4+5}
{2，5，7}和{1，3，4，6}
{3，4，7}和{1，2，5，6}
{1，2，4，7}和{3，5，6}
給定n，妳的程序應該輸出分區方案的總數，如果沒有這樣的分區方案，輸出0。程序不能存儲結果並直接輸出。
程序名稱:子集
輸入格式
輸入文件只有壹行，只有壹個整數n。
示例輸入(文件subset.in)
七
輸出格式
輸出分區方案的總數，如果不存在則輸出0。
示例輸出(文件subset.out)
四
參考程序如下(C語言):
# include & ltfstream & gt
使用命名空間std
const無符號int MAX _ SUM = 1024；
int n；
無符號long long int dyn[MAX _ SUM]；
ifstream fin(" subset . in ")；
of stream fout(" subset . out ")；
int main() {
fin & gt& gtn；
fin . close()；
int s = n *(n+1)；
如果(s % 4) {
fout & lt& lt0 & lt& ltendl
fout . close()；
返回；
}
s/= 4；
int i，j；
dyn[0]= 1；
for(I = 1；我& lt= n；i++)
for(j = s；j & gt= I；j -)
dyn[j]+= dyn[j-I]；
fout & lt& lt(dyn[s]/2)& lt；& ltendl
fout . close()；
返回0；
}
USACO 2.3
最長前綴
題目如下:
在生物學中，壹些生物體的結構是由包含其元素的壹系列大寫字母來表示的。生物學家感興趣的是將長序列分解成稱為基本序列的較短序列。
如果集合p中的元素可以串聯(允許重復；串聯，相當於Pascal中的“+”運算符)構成了壹個序列S，那麽我們認為序列S可以分解成p中的元素，並不是所有的元素都必須出現。例如，序列ABABACABAAB可以分解為以下集合中的元素:
{英國廣播公司，英國廣播公司，加拿大廣播公司}
序列s的前k個字符稱為s中長度為k的前綴，設計壹個程序，輸入壹個元素集和壹個大寫字母序列，計算這個序列最長前綴的長度。
程序名:前綴
輸入格式
輸入數據的開始包括壹組1...200個元素(長度為1...10)，用空格分隔的連續字符串表示。所有字母大寫，數據可能不止壹行。元素集合的結尾由壹條僅包含壹個“.”的線標記。集合中的元素不會重復。後跟大寫字母序列S，長度為1...200，000，用壹行或多行字符串表示，每行不超過76個字符。換行符不是序列s的壹部分
示例輸入(文件前綴. in)
英國廣播公司
。
ABABACABAABC
輸出格式
只有壹行，輸出壹個整數，表示S能分解成p中元素的最長前綴的長度。
示例輸出(文件前綴. out)
11
示例程序如下:
# include & ltstdio.h & gt
/*最大基元數*/
#定義MAXP 200
/*圖元的最大長度*/
#定義MAXL 10
char prim[MAXP+1][MAXL+1]；/*原語*/
int nump/*基元數*/
int start[200001]；/*序列的這個前綴是可表達的嗎？*/
char數據[200000]；/*序列*/
int ndata/*序列的長度*/
int main(int argc，char **argv)
{
FILE *fout，* fin
int最佳；
int lv，lv2，lv3
if ((fin = fopen("prim.in "，" r ")= = NULL)
{
perror(“fopen fin”)；
退出(1)；
}
if ((fout = fopen("prim.out "，" w")) == NULL)
{
perror(" fopen fout ")；
退出(1)；
}
/*讀入原語*/
while (1)
{
fscanf (fin，" %s "，prim[nump])；
if (prim[nump][0]！= '.')nump++；
else break
}
/*讀入字符串，壹次壹行*/
ndata = 0；
while (fscanf (fin，" %s "，data+ndata) == 1)
ndata+= strlen(data+ndata)；
start[0]= 1；
最佳= 0；
for(LV = 0；lv & ltndatalv++)
if (start[lv])
{ /*對於每個可表達的前綴*/
最好= lv/*我們找到了壹個更長的可表達前綴！*/
/*對於每個圖元，確定從開始的序列
這個位置與之匹配*/
for(lv2 = 0；lv2 & ltnumplv2++)
{
for(lv3 = 0；LV+lv3 & lt；ndata & amp& amp普裏姆[2級][3級]& amp；& amp
prim[lv2][lv3]= = data[LV+lv3]；lv3++)
如果(！prim[lv2][lv3]) /*匹配了！*/
start[LV+lv3]= 1；/*所以擴展前綴也很有表現力*/
}
}
/*查看整個序列是否可表達*/
if(start[ndata])best = ndata；
fprintf (fout，" %i\n "，best)；
返回0；
}
USACO 3.1
分數膨脹
題目如下:
我們試圖設計我們的比賽，以便人們可以盡可能多地得分，我們需要妳的幫助。
我們可以從幾個類別中選擇競賽題目。在這裏，壹個“類別”指的是壹個競賽題目的集合，解決集合中的題目所花的時間相同，可以得到相同的分數。
妳的任務是寫壹個程序，告訴USACO的工作人員應該從每個類別中選擇多少個問題，以便解決問題的總時間在比賽規定的時間內，並且總分是最大的。
輸入包括比賽的時間，m (1
隨後的每壹行將包括兩個整數來描述壹個“類別”:
第壹個整數表示分數(1
妳的程序應該確定我們應該從每個“類別”中選擇多少個主題，以便在比賽時間內獲得最高分。
來自任何“類別”的問題數量可以是任何非負數(0或更多)。
計算可能的最高分。
程序名稱:膨脹
輸入格式
第65438行+0: m，n-比賽時間和題目“類型”數量。
第2行-N+1:兩個整數:每個“類別”題目的分值和耗時。
示例輸入(文件inflate.in)
300 4
100 60
250 120
120 100
35 20
輸出格式
單行包括在給定限制內可以獲得的最高分數。
示例輸出(文件inflate.out)
605
{從第二個“類別”中選擇兩個問題，從第四個“類別”中選擇三個問題}
示例程序如下:
# include & ltfstream.h & gt
ifstream fin(" inflate . in ")；
of stream fout(" inflate . out ")；
const short maxm = 10010；
long best[maxm]，m，n；
空的
主()
{
短I，j，len，pts
fin & gt& gtm & gt& gtn；
for(j = 0；j & lt= m；j++)
best[j]= 0；
for(I = 0；我& ltn；i++) {
fin & gt& gtpts & gt& gtlen
for(j = len；j & lt= m；j++)
if(best[j-len]+pts & gt；最佳[j])
best[j]= best[j-len]+pts；
}
fout & lt& lt最佳[m]& lt；& ltendl//因為數組元素沒有減少，所以最後壹個元素最大。
}
USACO 3.3
壹個遊戲
題目如下:
有壹個雙人博弈如下:n (2
寫壹個實現最優策略的程序，最優策略是在當前情況下，能使妳獲得盡可能大的總分的策略。妳的程序應該總是為第二個玩家執行最優策略。
程序名稱:game1
輸入格式
第壹行:正整數n，表示序列中正整數的個數。
末尾第二行:n個正整數(大小1-200)，用空格隔開。
示例輸入(文件game1.in)
六
4 7 2 9
5 2
輸出格式
只有壹行，兩個用空格隔開的整數:依次是玩家1和玩家2的最終得分。
示例輸出(文件game1.out)
18 11
參考程序如下:
# include & ltstdio.h & gt
#定義NMAX 101
int best[NMAX][2]，t[NMAX]；
int n；
空的
readx () {
int i，aux
freopen ("game1.in "，" r "，stdin)；
scanf ("%d "，& ampn)；
for(I = 1；我& lt= n；i++) {
scanf ("%d "，& ampaux)；
t = t[I-1]+aux；
}
fclose(stdin)；
}
內嵌int
min (int x，int y) {
return x & gty？y:x；
}
空的
solve () {
int i，l；
for(l = 1；l & lt= n；l++)
for(I = 1；I+l & lt；= n+1；i++)
best[l % 2]= t[I+l-1]-t[I-1]-min(best[I+1][(l-1)% 2)，
best[(l-1)% 2])；
}
void writex () {
freopen ("game1.out "，" w "，stdout)；
printf ("%d %d\n "，best[1][n % 2]，t[n]-best[1][n % 2])；
fclose(stdout)；
}
（同Internationalorganizations）國際組織
main () {
readx()；
solve()；
writex()；
返回0；
}
USACO 3.4
喧鬧的搖滾樂手
題目如下:
您剛剛獲得了未發布的N (1
可惜妳是古典音樂迷，不知道如何判斷這些歌曲的藝術價值。所以妳決定根據以下標準進行選擇:
歌曲必須按照創作的時間順序出現在CD上。
盡可能多地選擇歌曲。
節目名稱:搖滾樂隊
輸入格式
第壹行:三個整數:n，t，m。
第二行:n個整數，分別代表每首歌的長度，按時間順序排列。
示例輸入(文件rockers.in)
4 5 2
4 3 4 2
輸出格式
壹個整數，表示m張CD光盤可以容納的最大音樂數量。
示例輸出(文件rockers.out)
三
參考程序如下:
# include & ltstdio.h & gt
#定義最大25
int dp[MAX][MAX][MAX]，length[MAX]；
（同Internationalorganizations）國際組織
主()
{
FILE *in = fopen ("rockers.in "，" r ")；
FILE *out = fopen ("rockers.out "，" w ")；
int a，b，c，d，best，numsongs，cdlength，numcds
fscanf (in，" %d%d%d "，& ampnumsongs & amp；cdlength & amp；num CDs)；
for(a = 1；a & lt= numsongsa++)
fscanf(在“%d”中，& amp長度[a])；
最佳= 0；
for(a = 0；a & ltnumcdsA++)/*當前cd */
for(b = 0；b & lt= cdlengthB++) /*經過的時間*/
for(c = 0；c & lt= numsongsC++) {/*上壹首*/
for(d = c+1；d & lt= numsongsD++) {/*下壹首*/
if(b+length[d]& lt；= cdlength) {
if(DP[a][c]+1 & gt；dp[a][b +長度[d]][d])
dp[a][b +長度[d]][d]= DP[a][c]+1；
}
否則{
if(DP[a][c]+1 & gt；DP[a+1][長度[d]][d])
DP[a+1][長度[d]][d]= DP[a][c]+1；
}
}
if (dp[a][c]>最佳)
best = DP[a][c]；
}
fprintf (out，" %d\n "，best)；
返回0；
}
USACO
4.3低買，低買
“抄底”是炒股成功的秘訣。如果妳想成為壹個成功的投資者，妳必須遵循這個秘密:
“逢低吸納，越跌越買。”
妳每買壹只股票，股價壹定要比上壹次買的時候低。按照這個規律買壹只股票的次數越多越好。看妳按照這個規律最多能買幾次。
給定連續n天每天的股價。您可以在任何壹天購買壹次股票，但購買時的股價必須低於您最後壹次購買時的股價。寫壹個程序，找出妳最多可以買多少次股票。
以下表為例。某壹天的股票價格是:
天數123456789 1011112
股價68 69 54 68 64 70 67 78 62 98 87
在這個例子中，壹個聰明的投資者(如上定義)最多可以買四次股票，如果他每次買股票的股價都比上壹次低的話。壹種購買方式如下(可能還有其他購買方式):
第2 5 6 10天
股價69 68 64 62
計劃名稱:buylow
輸入格式
第1行:n (1
第2行下面:n個正整數(可能分多行)，第I個正整數代表第I天的股價。這些正整數的大小不會超過long (Pascal)/long (c++)。
示例輸入(文件buylow.in)
12
68 69 54 64 68 64 70 67
78 62 98 87
輸出格式
只有壹行，輸出兩個整數:
妳可以購買股票的天數。
具有該長度的股票購買方案的數量。
在計算解的個數時，如果兩個解的字符串相同，那麽這樣的兩個解被認為是相同的(只有壹個解)。因此，兩個不同的采購方案可能產生相同的字符串，只能計算壹次。
示例輸出(文件buylow.out)
4 2
參考程序如下:
# include & ltstdio.h & gt
# include & ltassert.h & gt
# include & ltstdlib.h & gt
typedef struct BIGNUM * BIGNUM _ t；
結構BIGNUM
{
int val
bignum _ t next
};
int num[5000]；
int len[5000]；
int nlen
bignum _ t CNT[5000]；
bignum_t get_big(void)
{
靜態bignum_t塊；
靜態int size = 0；
如果(大小== 0)
{
block =(bignum _ t)malloc(sizeof(* block)* 128)；
size = 128；
}
尺寸-；
返回block++；
}
/*初始化高精度度*/
void init_big(bignum_t *num，int val)
{
* num = get _ big()；
/*初始化*/
(*數字)-& gt；val = val
(*數字)-& gt；next = NULL
}
void add(bignum_t a，bignum_t b)
{
int c；/*進位*/
c = 0；
while (b || c)
{
a-& gt；val+= c；
如果(b)a-& gt；val+= b-& gt；val
/*如果a-& gt；val太大，我們需要攜帶*/
c =(a-& gt；val/1000000)；
a-& gt；val =(a-& gt；val % 1000000)；
如果(b)b = b-& gt；接下來；
如果(！a-& gt；next & amp& amp(b || c))
{ /*需要時分配*/
a-& gt；next = get _ big()；
a = a-& gt；接下來；
a-& gt；val = 0；
a-& gt；next = NULL
} else a = a-& gt；接下來；
}
}
void out_num(FILE *f，bignum_t v)
{
如果(v-& gt；下壹個)
{
out_num(f，v-& gt；下壹個)；
fprintf (f，" %06i "，v-& gt；val)；
}
其他
fprintf (f，" %i "，v-& gt；val)；
}
int main(int argc，char **argv)
{
FILE *fout，* fin
int lv，lv2
int c；
int max
int l；
bignum _ t ans
if ((fin = fopen("buylow.in "，" r ")= = NULL)
{
perror(“fopen fin”)；
退出(1)；
}
if ((fout = fopen("buylow.out "，" w")) == NULL)
{
perror(" fopen fout ")；
退出(1)；
}
fscanf (fin，" %d "，& ampnlen)；
for(LV = 0；lv & ltnlenlv++)
fscanf (fin，" %d "，& ampnum[LV])；
/*用DP計算最大長度*/
for(LV = 0；lv & ltnlenlv++)
{
max = 1；
for(lv2 = LV-1；lv2 & gt= 0;lv2 -)
if(num[lv2]& gt；數字[呂]& amp；& amplen[lv2]+1 & gt；max)max = len[lv2]+1；
len[LV]= max；
}
for(LV = 0；lv & ltnlenlv++)
{
if(len[LV]= = 1)init _ big(& amp；cnt[lv]，1)；
其他
{
init _ big(amp；cnt[lv]，0)；
l =-1；
max = len[LV]-1；
for(lv2 = LV-1；lv2 & gt= 0;lv2 -)
if(len[lv2]= = max & amp；& ampnum[lv2]& gt；數字[呂]& amp；& ampnum[lv2]！= l)
add(cnt[lv]，CNT[lv2])；
l = num[lv2]；
}
}
}
/*查找最長的字符串*/
max = 0；
for(LV = 0；lv & ltnlenlv++)
if (len[lv]>max)max = len[LV]；
init _ big(amp；ans，0)；
l =-1；
for(LV = nlen-1；lv & gt= 0;lv -)
if(len[LV]= = max & amp；& ampnum[lv]！= l)
{
add(ans，CNT[LV])；
l = num[LV]；
}
/*輸出答案*/
fprintf (fout，" %i "，max)；
out_num(fout，ans)；
fprintf (fout，" \ n ")；
返回0；
}
動態規劃作為信息學算法中的壹個重要奧數，具有很強的靈活性。以上是壹些入門練習，深入學習需要逐步積累經驗。