珠海信息学奥赛培训 动态规划算法应用

来源：珠海童程童美少儿编程培训学院时间：2023/8/19 11:12:59

　　动态规划算法应用

　　例1：合唱队形(noip2004tg)

　　【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。你的任务是，已知所有N位同学的身高，计算较少需要几位同学出列，可以使得剩下的同学排成合唱队形。 【输入文件】输入文件chorus.in的第 一行是一个整数N(2 <= N <= 100)，表示同学的总数。行有n个整数，用空格分隔，第i个整数Ti(130 <= Ti <= 230)是第i位同学的身高(厘米)。

　　【输出文件】输出文件chorus.out包括一行，这一行只包含一个整数，就是较少需要几位同学出列。 【样例输入】8

　　186 186 150 200 160 130 197 220

　　【样例输出】 4

　　算法分析：此题采用动态规划法求解。先分别从左到右求较大上升子序列，从右到左求较大下降子序列，再枚举中间较高的一个人。算法实现起来也很简单，时间复杂度O(N^2)。

　　我们先考虑如何求较大上升子序列的长度，设f1(i)为前i个同学的较大上升子序列长度。若要求f1(i)，必须先求得f1(1),f1(2),…,f1(i-1)，再选择一个较大的f1(j)(j

　　设f2(i)为后面N-i+1位排列的较大下降子序列长度，用同样的方法可以得到状态转移方程：f2(i)=max{f2(j)+1} (i

　　t,f1,f2:array[1..100]of byte; i,j,n,max:integer; begin

　　assign(input,'chorus.in'); reset(input); readln(n); for i:=1 to n do begin

　　read(t[i]);f1[i]:=1;f2[i]:=1; end;{for}

　　close(input); max:=0; for i:=2 to n do

　　for j:=1 to i-1 do begin

　　if (t[i]>t[j])and(f1[j]>=f1[i]) then f1[i]:=f1[j]+1; {从左到右求较大上升子序列}

　　if (t[n-i+1]>t[n-j+1])and(f2[n-j+1]>=f2[n-i+1]) then f2[n-i+1]:=f2[n-j+1]+1; {从右到左求较大下降子序列} end;{for}

　　for i:=1 to n do if max

　　运用动态规划法求解问题的关键是找出状态转移方程，只要找出了状态转移方程，问题就解决了一半，剩下的事情就是解决如何把状态转移方程用程序实现。

　　例2、乘积较大(noip2000tg)

　　题目大意：在一个长度为N的数字串中插入r个乘号，将它分成r+1个部分，找出一种分法，使得这r+1个部分的乘积较大。

　　算法分析：此题满足动态规划法的求解标准，我们把它按插入的乘号数来划分阶段，若插入K个乘号，可把问题看做是K个阶段的决策问题。设f[i,k]表示在前i位数中插入K个乘号所得的较大值，a[i,j]表示从第i位到第j位所组成的自然数。用f[i,k]存储阶段K的每一个状态，可以得状态转移方程： f[i,k]=max{f[j,k-1]*a[j+1,i]}(k<=j<=i) 边界值：f[j,0]=a[1,j] (1

　　根据状态转移方程，我们就很容易写出动态规划程序： for k:=1 to r do for i:=k+1 to n do for j:=k to I do

　　if f[i,k]

　　近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOIP都至少有一道题目需要用动态规划法求解。而应用动态规划法解题是富于技巧性和创造性的，虽然在前面的求解过程中给出了一个解题的基本模式，但由于动态规划题目出现的形式多种多样，并且大部分题目表面上看不出与动态规划的直接联系，只有在充分把握其思想精髓的前提下大胆联想，多做多练才能达到得心应手，灵活运用的境界。

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/970/news/652455/违者必究！ 以上就是珠海童程童美少儿编程培训学院 小编为您整理 珠海信息学奥赛培训 动态规划算法应用的全部内容。