动态规划讲解

线性动规

LIS类型DP

【例题1】：最长不下降序列1078

Description:

设有整数序列b1,b2,b3,……,bm, 若存在i1< i2

第一行为一个数n，表示有n个数，第二行为n个整数序列； Output:

第一行为最大长度，第二行为满足长度的序列 Sample Input 14

13 7 9 16 38 24 37 18 4 19 21 22 63 15 Sample Output 8

7 9 16 18 19 21 22 63 【试题分析】

1、阶段和状态：

f[i]：表示以a[i]为最后一个数字的最长不下降序列的最大长度；

阶段i表示前i个数，由于每个阶段只有一个状态，所以用一维数组表示； 2、状态转移方程： 初始化：f[i]=1;

f[i]=max{f[j]+1,j

初始化： i a[i] f[i] 1 13 1 2 7 1 0 3 9 1 0 4 5 6 7 8 9 4 1 0 10 11 12 13 14 19 21 22 63 15 1 0 1 0 1 0 1 0 1 0 16 38 24 37 18 1 0 1 0 1 0 1 0 1 0 pre[i] 0

计算过程： i a[i] f[i] 1 13 1 2 7 1 2 3 9 2 2 4 5 6 7 8 9 4 1 9 10 11 12 13 14 19 21 22 63 15 5 8 6 7 8 3 3 16 38 24 37 18 3 3 4 4 4 4 5 6 4 4 pre[i] 1

10 11 12

3、核心子程序： 说明 数组p[i]记录第i个数前一个结点下标。 void out(int pre[],int a[],int n) //递归输出序列 { if (pre[n]==n){cout<>n; for(i=1;i<=n;i++) {cin>>a[i];f[i]=1;pre[i]=i;}//初始化 for(i=2;i<=n;i++) for(j=1;jf[i]){f[i]=f[j]+1;pre[i]=j;} max=1; for(i=1;i<=n;i++) if(f[i]>f[max])max=i; cout<

【例题2】渡轮问题1373

Description

有一个国家被一条河划分为南北两部分，在南岸和北岸总共有N对城镇，每一城镇在对岸都有唯一的友好城镇。任何两个城镇都没有相同的友好城镇。每一对友好城镇都希望有一条航线来往。于是他们向政府提出了申请。由于河终年有雾。政府决定不允许有任两条航线交叉(如果两条航线交叉，将有很大机会撞船)。

你的任务是写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使得没有出现交叉的航线最多。 Input

第一行一个整数N(1 <= N <= 1000)，表示分布在河两岸的城镇对数。

接下来的N行每行有两个由空格分隔的正数C，D ( C、D<=10^9 )，描述每一对友好城镇沿着河岸与西边境线的距离，C表示北岸城镇的距离而D表示南岸城镇的距离。在河的同一边，任何两个城镇的位置都是不同的。 Output

在安全条件下能够开通的最大航线数目。 Sample Input 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2

Sample Output 4

【试题分析】：

1、阶段和状态：题目粗略一看，不能够用动态规划求解，因为具有后效性,但是仔细分析如果先按照a[i]从小到大排序后,解除了后效性,问题变成了对于b[i]求最长上升子序列问题

f[i]:表示以b[i]为最后一个数字的最长不下降序列的最大长度

注意：好多题目都要通过排序解除后效性！！

2、状态转移方程： 初始化：f[i]=1;(1<=i<=n) f[i]=max{f[j]+1,j

【例题3】合唱队形1001

Description

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得TiTi+1>......>TK。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 Input

输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。 Output

输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。 Sample Input

8

186 186 150 200 160 130 197 220 Sample Output

4

数据规模

对于50％的数据，保证有n<=20； 对于全部的数据，保证有n<=100。

【试题分析】

动态规划。最基本的想法是：枚举中间最高的一个人，接着对它的左边求最长上升序列（注意序列中最高的同学不应高过基准），对右边求最长下降序列（同样的，序列中最高的同学不应高过基准）。时间复杂度为O(n^3)，算法实现起来也很简单。

接着对这个算法进行分析，我们不难发现，假如还是基于枚举一个同学的话，设Incsq[i]表示了1 - i的最长上升序列，Decsq[i]表示了i - n的最长下降序列，那么， Current[i] = Incsq[i] + Decsq[i] - 1（两个数组中i被重复计算了）

那么，我们只需要先求好最长上升和下降序列，然后枚举中间最高的同学就可以了。

【算法优化】

求最长上升序列的经典状态转移方程为： opt[i] = max{opt[j]+1, 其中ilist[i]}

我们对状态转移方程稍微做一些修改： opt[i] = max{opt[i+1], min{j, rec[j]>=list[i]}} rec[j] = list[i]

很明显可以看出，在opt[i]的寻找j的过程当中，查询序列是单调的，于是可以用二分法，就十分巧妙地在logn的时间内找到指定的j，而问题的总体复杂度为O(nlogn)。这样，这个问题的算法效率就得到了大幅度的提升，即便n是106，也可以轻松应对。 【C参考代码】

#include #include using namespace std;

ifstream fin(\ ofstream fout(\

const int maxn = 100;

int n, a[maxn];

int incsq[maxn], decsq[maxn];

void init() { fin >> n;

for (int i = 0; i < n; i ++) fin >> a[i]; }

void LIncSeq() {

int i, low, high, mid, ans = 0; int sol[maxn];

for (i = 0; i < n; i ++) { low = 1; high = ans; while (low <= high) { mid = (low + high) >> 1; if (sol[mid] < a[i]) low = mid + 1; else high = mid - 1; }

if (low > ans) ans ++;

sol[low] = a[i]; incsq[i] = ans; } }

void LDecSeq() {

int i, low, high, mid, ans = 0; int sol[maxn];

for (i = 0; i < n; i ++) { low = 1; high = ans; while (low <= high) { mid = (low + high) >> 1; if (sol[mid] > a[i]) low = mid + 1; else high = mid - 1; }

if (low > ans) ans ++; sol[low] = a[i]; decsq[i] = ans; } }

void work() { int i, max = 0;

LIncSeq(); LDecSeq();

for (i = 0; i < n; i ++)

if (incsq[i] + decsq[i] - 1 > max) max = incsq[i] + decsq[i] - 1;

fout << n - max << endl; }

int main() { init();

work(); return 0; }

【小结】

问题虽然简单，仍然不能放过思考的余地。O(n^3)的算法是可以通过所有测试数据的，但是nlogn的算法里，不但体现了二分法的思想，而且也体现了多次动态规划的思想，这个思想在解决很多问题的时候，都有很大的作用。

【例题4】飞翔1907

Description

鹰最骄傲的就是翱翔，但是鹰们互相都很嫉妒别的鹰比自己飞的快，更嫉妒其他的鹰比自己飞行的有技巧。于是，他们决定举办一场比赛，比赛的地方将在一个迷宫之中。 这些鹰的起始点被设在一个N*M矩阵的左下角map[1，1]的左下角。终点被设定在矩阵的右上角map[N,M]的右上角，有些map[i,j]是可以从中间穿越的。每一个方格的边长都是100米。如图所示：

没有障碍，也没有死路。这样设计主要是为了高速飞行的鹰们不要发现死路来不及调整而发生意外。潘帕斯雄鹰冒着减RP的危险从比赛承办方戒备森严的基地中偷来了施工的地图。但是问题也随之而来，他必须在比赛开始之前把地图的每一条路都搞清楚，从中找到一条到达终点最近的路。（哈哈，笨鸟不先飞也要拿冠军）但是此鹰是前无古鹰，后无来鹰的吃菜长大的鹰--菜鸟。他自己没有办法得出最短的路径，于是紧急之下找到了学OI的你，希望找到你的帮助。 Input

首行为n,m(0 < n,m<= 100000),第2行为k（0 < k<= 1000）表示有多少个特殊的边。以

下k行为两个数，i,j表示map[i,j]是可以直接穿越的。 Output

仅一行，1，1-->n,m的最短路径的长度，四舍五入保留到整数即可 Sample Input 3 2 3 1 1 3 2 1 2

Sample Output 383 【试题分析】

【例题５】buy low，buy lower逢低吸纳

“低价购买”这条建议是在奶牛股票市场取得成功的一条规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议：“低价购买；再低价购买”。每次你购买一支股票，你必须用低于你上次购买股票的价格购买它。买的次数越多越好！你的目标是在遵循以上建议的前提下，求你最多能够购买股票的次数。你将会得到一段时间内一支股票每天的出售价（2^16范围内的正整数），你可以选择在那些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一程序计算最大购买次数。 这里是某支股票的价格清单： 日期 1 2 3 4 5 6 7 8 9 10 11 12

价格 68 69 54 64 68 64 70 67 78 62 98 87

最优秀的投资者可以购买最多4次股票，可行方案中的一种是： 日期 2 5 6 10 价格 69 68 64 62 Input

第一行：n（1 <= n <= 5000），股票发行天数；第二行：n个数，是每天的股票价格。 Output

输出文件仅一行包含两个数：最大购买次数和拥有最大购买次数的方案数（小于等于2^16）当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候），这2种方案被认为是相同的。

【试题分析】

问题的第一部分是要求得到输入数据串中的一个最长下降序列的长度，可使用动态规划的方法。具体做法是从序列的最后一个元素开始，依次求出以第i个元素为第一个元素时的最长下降序列的长度len[i]，显然len[n]=1，len[i]=max(len[j]+1)，其中i

第二部分比较有难度。由于它紧接着第一问，所以一般说来应该充分利用第一个问题的结论，对于任意一个最长下降序列，设它的第一个元素的下标为i1，第二个元素的下标为i2，其余元素的下标以此类推，则显然有len[i1]=maxlen，len[i2]=maxlen-1，…，现在要求所有不同的最长下降序列的总数，则只要求按照数组len的值从小到大对整个序列从后向前递推即可。以序列a=(5,3,1,4,2)为例。Len[1]=3，len[2]=2，len[3]=1，len[4]=2，len[5]=1，用t[i]记录以第i个元素为头一个元素到序列结束为止的最长下降序列的不同方案总数，若len[i]=1，则t[i]=1，本例中由len[3]=1，len[5]=1可知t[3]=1，t[5]=1，再由len[5]=1，len[4]=2且a[4]=4>a[5]=2可得t[4]=1，由len[5]=1,len[2]=2且a[2]=3>a[5]=2和len[3]=1,len[2]=2且a[2]=3>a[3]=1可得t[2]=t[5]+t[3]=2，对应{a[2],a[3]}和{a[2],a[5]}两个不同的以a2起头的最长下降序列，最终由len[4]=2,len[1]=3且a[1]=5>a[4]=4和len[2]=2,len[1]=3且a[1]=5>a[2]=3可得t[1]=t[4]+t[2]=1+2=3，所以本例中最长下降序列总数为3，分别为{5，4，2}，{5，3，2}和{5，3，1}。对于有相同元素的序列来说，如序列a=(5，4，1，4，2)，其中有两个相同的元素4，前面的推导过程不变，最后一步推导受两个相同元素的影响，不能简单相加，由于a2=a4=4，对于所有的以a4起头的最长下降序列，只要将a4改为a2即可得到同样长度的下降序列，所以t[4]中的统计的序列在t[2]中也统计在内了，当序列中有相同元素时，为避免重复计数，从后向前递推时当后面的元素遇到前面的相同元素时则不再向前推。程序中为了方便处理，在整个序列前设置了一个标识元素a[0]=maxlongint,将len[0]置为maxlen+1。

#include int n;

int date[5005]; int st[5005];//长度 int sum[5005];//方案 int res1 = 0, res2 = 0; int main() { scanf(\ int i, j; for(i=1; i<=n; i++) scanf(\ for(i=n; i>=1; i--) { st[i] = sum[i] = 1; for(j=i+1; j<=n; j++) { if(date[j] < date[i]) { if(st[j] >= st[i]) { st[i] = st[j]+1; sum[i] = sum[j]; } else if(st[j] == st[i]-1) sum[i] += sum[j]; } else if(date[j] == date[i]) {

sum[j] = 0; } } } for(i=1; i<=n; i++) { if(st[i] > res1) { res1 = st[i]; res2 = sum[i]; } else if(st[i] == res1) res2 += sum[i]; } printf(\ return 0; }

下面的程序采用了hash判重来处理相同的数 #include using namespace std;

int a[5001],f[5001],p[5001]; bool hash[30001]; int main() {

int n,i,j; cin>>n;

memset(p,0,sizeof(p));

for(i=1;i<=n;i++) {scanf(\ p[n]=1;

for(i=n-1;i>=1;i--) {

for(j=i+1;j<=n;j++)

if(a[j]f[i]) f[i]=f[j]+1; if(f[i]==1) {p[i]=1;continue;} memset(hash,0,sizeof(hash)); for(j=i+1;j<=n;j++)

if(a[j]

int max=1,sum=0;

for(i=2;i<=n;i++) if(f[i]>f[max]) max=i; cout<

memset(hash,0,sizeof(hash));

for(i=1;i<=n;i++) if(f[i]==f[max]&&hash[a[i]]==0) {sum+=p[i];hash[a[i]]=true;} cout<

附：最长上升子序列(LIS)的O(nlogn)算法

思想：以a[i]结尾的长度为x上升子序列，若a[i]越小的话则后面长度增长的可能性更大。当前面有多个同等长度的序列时，我们只需存储尾部元素最小的即可。这样，我们存储的所有这样的尾部元素序列就变为一个上升序列，序列的长度就为最终所求。

开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈（加长了一位）；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它(换了一个小的)。 最长序列长度即为栈的大小top。

这也是很好理解的，对于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x]

替换Stack[y]，此时的最长序列长度没有改变但序列Q的''潜力''增大了。 举例：原序列为1，5，8，3，6，7

栈为1，5，8，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。

#include using namespace std; int main()

{

int i, j, n, top, temp; int stack[1001]; cin >> n; top = 0;

/* 第一个元素可能为0 */ stack[0] = -1;

for (i = 0; i < n; i++) {

cin >> temp;

/* 比栈顶元素大数就入栈 */ if (temp > stack[top]) {

stack[++top] = temp; } else {

int low = 1, high = top; int mid;

/* 二分检索栈中比temp大的第一个数 */ while(low <= high) {

mid = (low + high) / 2; if (temp > stack[mid]) {

low = mid + 1; } else {

high = mid - 1; } }

/* 用temp替换 */ stack[low] = temp; } }

/* 最长序列数就是栈的大小 */ cout << top << endl; return 0; }

递推类型DP

【例题1】：数字三角形1077

Description

如下所示一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。

●每一步可沿左斜线向下或右斜线向下走； ●1＜三角形行数≤100；

●三角形中的数字为整数0，1，…99；

Input：输入第一行为一个自然数，表示数字三角形的行数n，接下来的n行表示一个数字三

角形．

Output：输出仅有一行包含一个整数（表示要求的最大总和） Sample Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

Sample Output：30

【试题分析】

（1）从底层开始，本身数值即为最大数。

（2）倒数第二层的计算，将决定于底层。 （3）最后路径为13---8----26---8-24

1、阶段和状态：本题是一个非常典型的递推类型的数字三角形问题。由于每层是相互独立，不互相影响的，所以此题可以以每一层为阶段用动态规划求解。

a[i][j]：表示各点的数字值;

f[i][j]：表示从第n层到(i,j)这点，该路径所经过的数字的最大总和； 阶段：层数i；状态：列数j 1、 状态转移方程：

初始值：f[n][i]=a[n][i];(1<=i<=n)

状态转移方程：f[i][j]=max{f[i+1][j]，f[i+1][j+1]}+a[i][j]; (1<=i<=n-1;1<=j<=i) Answer=f[1][1]

3、核心子程序： int main () { int i,j; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=i;j++)cin>>a[i][j]; //读入数据 for(i=1;i<=n;i++)f[n][i]=a[n][i]; //初始化 for (i=n-1;i>=1;i--) //阶段行数 for (j=1;j<=i;j++) //状态列数 f[i][j]=maxx(f[i+1][j]+a[i][j],f[i+1][j+1]+a[i][j]);//决策 cout<

思考：

数字三角形II：有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，如下图所示。

数字三角形问题II

从第一行的数开始，除了某一次可以走到下一行的任意位置外，每次都只能左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来。如何走，使得这个和尽量大？

稍微修改一下以后，原来的解法不适用了，如果仍然记d[i,j]为以格子(i,j)为根的子三角形的解，那么第一步到底是可以任意移动，还是只能往左下或右下走一格呢？不一定，这取决于解决这个子问题之前做过什么事。

后效性：刚才的状态定义有后效性（无后效性有时也称子问题的独立性），即先前的决策可能影响后续的决策。解决方法是扩展状态定义，把有后效性的部分包含进来。记d[i][j][k]为以格子(i,j)为根的子三角形的解，k=1表示可以任意移动，k=0表示不能任意移动，则原来问题的解是d[1][1][1]。当k=1时可以任意移动，然后k=0，而k=0时不能任意移动。状态转移方程需要分类讨论，写成程序是：

if(i==n)d[i][j][k]=a[i][j];

else { d[i][j][k]=max(d[i+1][j][k],d[i+1][j+1][k]); // normal move

if(k==1) // teleport for (t=1;t<=i;i++)

if(d[i][j][k]

}

当然，所有d[i][j][0]的最大值可以边计算边记录，像这样： memset (max,0,sizeof(max)); for (j=1;j<=n;j++)

{ d[n][j][1]=d[n][j][0]=a[n][j];

if(a[n][j]>max[n]) max[n]=a[n][j]); }

for (i=n-1;i>=1;i--) { for(j=1;j<=i;j++)

{ d[i][j][0]=max(d[i+1][j][0],d[i+1][j+1][0]); // normal move if(d[i][j][0]>max[i]) max[i]=d[i][j][0]; // update max d[i][j][1]=max(d[i+1][j][1],d[i+1][j+1][1],max[i+1]);

// normal move / teleport

} }

免去了一次循环，时间复杂度仍为O(n2)。

数字三角形III：有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，如下图所示。

数字三角形问题III

从第一行的数开始，每次都只能左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来。如何走，使得这个和的个位数尽量大？

这次没有后效性了，但是又有了新的问题。

错误方程1：d[i][j]=max{d[i+1][j],d[i][j+1]}+a[i][j]。反例：如果d[i+1][j] =5，d[i][j+1]=6，a[i][j]=9，那么加起来是14或15，是两位数；

错误方程2：d[i][j]=(max{d[i+1][j], d[i][j+1]}+a[i][j]) mod 10。反例：d[i+][j]=6, d[i][j+1]=9，a[i][j]=2，虽然6比9小，但是6+2的个位数比9+2的个位数大。

错误方程3：d[i][j]=max{(d[i+1][j]+a[i][j])mod 10, (d[i+1][j+1]+a[i][j]) mod 10}。这个错误比较隐蔽，它并不是来源于方程本身的错误，而是状态定义的错误。

方程三错误示意图

数字三角形上的数如上图。对于灰色格子(2,1)来说，根据状态定义，d[2][1]=6（从此格子出发路径上数之和的最大个位数），d[2][2]=0（无论怎么走，个位数都是0），根据前面的“递推方程”算出d[1][1]应是1，但实际上d[1][1]等于9。事实上，对于相同的d[2][1]和d[1][1]可能会有不同的d[1][1]，所以不存在从d[2][1]和d[2][2]得到d[1][1]的递推公式！也就是说，并不能怪我们没有找到正确的状态转移方程，实在是因为这样的状态定义根本无法递推！

问题出在哪里呢？关键是：全局最优解5-0-4-0并没有包含子问题最优解0-4-2。由于d值只保留“子问题最优解”，当全局最优解并没有包含子问题最优解时，d值无法递推。

【最优子结构】在贪心法介绍中曾经提到过最优子结构。这样的结构在动态规划中也是需要的。不满足最优子结构的情况通常也可以考虑扩展状态定义。在本例中，记d[i][j][k]表示以格子(i,j)为根的子三角形是否存在所有数之和个位为k的路径，则d[i][j][k]为真当且仅当存在t使得(a[i][j]+t) mod 10=k，且d[i+1][j][t]或d[i+1][j+1][t]为真。 memset (d,0,sizeof (d )); // false

for (j=1;j<=n;j++) d[n][j][a[n][j]]=true ; for (i=n-1;i>=1;i--) for (j=1;j<=i;j++)

for (k=0;k<=9;k++) { d[i][j][k]=false ;

for(t=0;t<=9;t++) // lookup suitable t

if ((a[i][j]+t )==k && (d[i+1][j][t]||d[i+1][j+1][t]))

d[i][j][k]=true ;

}

这个程序是对的，但稍稍有点别扭。如果a[i][j]=5和k=5，需要检查的只有t=0，不需要从0到9依次判断一次，即： for (i=n-1;i>=1;i--) for (j=1;j<=i;j++)

for (k=0;k<=9;k++) { d[i][j][k]=false ;

t=(10-a[i][j]) % 10;

if(d[i+1][j][t]||d[i+1][j+1][t]))d[i][j][k]=true ; }

2

这样就避免了内层循环，时间复杂度为O(n)。看上去本题已经很好的解决了，但如果把加法改为乘法呢？还是a[i][j]=5和k=5的情况，需要检查的t有1,3,5,7或9五个，而不是一个。在这样的情况下，是否仍然可以避免内层循环呢？答案是肯定的，不过要稍微调整一下算法。

不妨把刚才的程序称为“综合法”，即按照一定的顺序依次计算每个状态的值。如果一个状态需要用k状态来计算（比如在刚才的例子中，一个状态需要t = 1, 3, 5, 7, 9五个状态计算），称这个状态的决策量为k。综合法的时间复杂度为O(状态个数×平均每个状态的决策数)，或O(总决策数)。对于特殊的问题，综合法并不是最好的。因为它会检查很多状态。更新法写起来更加简单，且时间效率更高： for (i=n;i>=1;i--) for (j=1;j<=i;j++)

for (k=0;k<=9;k++) if(d[i][j][k])

d[i-1][j][(k*a[i-1][j])] =d[i-1][j-1][(k*a[i-1][j-1])]=true ;

虽然一个状态需要用很多状态计算，但每个状态最多只能更新两个状态。更新法就是利用这一点避免无谓的判断。更新法同时适用于取max或min的情况，但不适合于两个状态需要做运算的情况。

【例题2】最小伤害2275

【问题描述】:把儿站在一个N x N的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。

【输入数据】:第一行输入一个正整数n。以下n行描述该矩阵。矩阵中的数保证是不超过1000的正整数。

【输出数据】:输出最小伤害值。 【样例输入】: 3 1 3 3 2 2 2 3 1 2

【样例输出】:8

【数据规模】: n<=1000 【试题分析】 1、阶段和状态：

f[i][j]：表示从(1,1)走到(i,j)时候的最小伤害值； 2、状态转移方程：

状态转移方程：f[i][j]=min{f[i-1][j],f[i][j-1]}+map[i][j]

初始值：f[0][i]=f[i][0]=0xfffffff; //相当于在上面和左面分别加一行和一列 answer=f[n][m]

3、核心子程序： cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf(“%ld”,&a[i][j]);//读入数据 for(i=2;i<=n;i++) {f[0][i]=0xfffffff; f[i][0]=0xfffffff;}//初始化 for(i=1;i<=n;i++) for(j=1;j<=n;j++) f[i][j]=minn(f[i-1][j],f[i][j-1])+a[i][j];

cout<

【例题3】：过河卒

Description：如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。

棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定: C<>A，同时C<>B）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。

Input：键盘输入B点的坐标（n,m）以及对方马的坐标（X,Y）{不用判错} Output：屏幕输出一个整数（路径的条数）。 Sample Input：6 6 3 2 Sample Output：17

【例题4】拾垃圾的机器人

有一块地被划分成了n*m个区域，在一些区域里有垃圾要拾捡。现在科研人员开发了一个能捡垃圾的机器人，机器人每一次都可以移动一个区域的距离，假设机器人从最左上区域出发，他每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。 问：该机器人最多能够拾多少垃圾？ 在最多情况下，有多少种方案？

【输入文件】：输入文件的第一行为两个整数n和m，接下来有一个n*m的01矩阵。矩阵中的第i行j列的数字a[i][j]=0表示为空地，a[i][j]=1表示为垃圾。

【输出文件】：输出文件的第一行为一个整数，表示该机器人拾到的最多垃圾数。第二行为一个整数，表示该机器人拾到的最多垃圾的路径总数。 【样例输入】： 6 7

0101000 0001010 0000000 0001001

0000000 0000010

【样例输出】

5 4

【数据范围】：n<=100,m<=100 【思路点拨】：我们先看样例，如图1，垃圾用G表示。假设机器人走到(i,j)这个位置，由于机器人只能向下向右走，那么机器人的上一个位置一定是(i-1,j)和(i,j-1)。

我们设机器人走到(i,j)位置时拾到最多垃圾数为f[i][j]，由于机器人只能朝右和下走，只会跟机器人上一位置拾到最多的垃圾数有关，因此很容易写出状态转移方程。

F[i][j]=max{f[i-1][j],f[i][j-1]}+a[i][j],1<=i<=n,1<=j<=m 初始值：f[0][0]=0 时间复杂度为：O(nm)

我们再来看第二问：在最优解的情况下求方案总数，我们只要每次在最优解的情况下统计路径条数即可，见图2：

设t[i][j]表示在位置(i,j)达到拾到f[i][j]垃圾时的路径总数，有如下方程： T[i][j]=t[i-1][j],当f[i][j]=f[i-1][j]+a[i][j]; (公式1) T[i][j]=t[i][j-1],当f[i][j]=f[i][j-1]+a[i][j]; (公式2)

其中公式1表示往右走能拾到最多的垃圾，公式2表示往下走能拾到最多垃圾。因此运用加法原理，综合公式1和公式2，可以写成如下形式：

T[i][j]=t[i-1][j]*L+t[i][j-1]*k

当f[i][j]=f[i-1][j]+a[i][j]时，L=1，否则L=0； 当f[i][j]=f[i][j-1]+a[i][j]时，k=1，否则k=0； 初始值：t[0][0]=0 时间复杂度为：O(nm)

思考：

【例题】晴天小猪历险记之Hill bsoi1670 【例题】方格取数bsoi1265 ？两次动规

两次动规的反例： 0 100 20 0 1000 30 0 10 0 ？先搜再动规

？两人同时取f[I,j,m,n] ? f[I,j,k]

【例题】三取方格数bsoi1720

资源分配类型DP 【例题1】机器分配2167 Description

总公司拥有高效生产设备M台，准备分给下属的N个公司。各个分公司若获得这些设备，

可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M <= 20，N <= 20。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。 Input

第一行为两个数，第一个数是设备台数M，第二个数是分公司数N。

接下来是一个N*M的矩阵，表明了第i个公司分配j台机器的盈利（都小于100）。 Output

分配这M台设备使国家所得到的盈利最大值 Sample Input

4 3 1 2 3 4 2 1 4 3 3 1 4 2 Sample Output

7 【算法分析】 1、 阶段和状态：

这是一个典型的动态规划试题。用公司数来做状态，数组f[i][j]表示前i个公司分配j台机器的最大盈利。

下标i公司数表示阶段，j机器数表示状态。题目要求的是： n个公司分配m台机器的最大盈利f[n][m]； 2、状态转移方程：

f[i][j]=max{f[i-1][k]+a[i][j-k]} (1<=i<=n,1<=j<=m,0<=k<=j ) 初始值: f[0][0]=0

时间复杂度o(n*m2)3、核心子程序：

3、核心子程序： int main() { cin>>m>>n; for(i=1;i<=n;i++) for(j=1;j<=m;j++)cin>>a[i][j];//读入第i个公司分配j台机器的盈利 memset(f,0,sizeof(f)); for(i=1;i<=n;i++) //公司数 核心 for(j=1;j<=m;j++) //机器数 代码 { maxx=0; for(k=0;k<=j;k++) //决策 if(maxx

【例题2】乘积最大1262 Description

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目:

设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串: 312，当N=3，K=1时会有以下两种分法： 1）3*12=36 2）31*2=62

这时，符合题目要求的结果是： 31*2=62

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 Input

程序的输入共有两行:

第一行共有2个自然数N,K (6<=N<=40，1<=K<=6) 第二行是一个K度为N的数字串。 Output

结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。 Sample Input 4 2 1231

Sample Output 62 【算法分析】 2、 阶段和状态：

sum[i][j]：表示在s串中从i开始到j结束的数值； f[i][j]：表示前i个字符中插入j各乘号所得的最大乘积； 2、状态转移方程：

初始化：f[i][0]=sum[1][i]; 状

态

转

移

方

程

：

f[i][j]=max{f[t][j-1]*sum[t+1][i]}(1<=j<=k,j+1<=i<=n,j<=t<=i-1)

answer=f[n][k]

3、核心子程序： int g(int a[],int bg,int ed) { int i,s=0; for(i=bg;i<=ed;i++)s=s*10+a[i]; return s; } int main() { int n,k,m,t,a[41],i,j,l,f[41][8]={0},sum[16][16]; char c; cin>>n>>k; //n个数，k个乘号

for(i=1;i<=n;i++){cin>>c;a[i]=c-‘0’;} //转换为数值 for(i=1;i<=n;i++) for(j=i;j<=n;j++)sum[i][j]=g(a,i,j); for(i=1;i<=n;i++)f[i][0]=sum[1][i]; //初始化 for(j=1;j<=k;j++) //乘号数目 for(i=j+1;i<=n;i++) //数字个数 { m=0; for(t=j;t<=i-1;t++) //决策前t个数字中添加j-1个乘号 if(m

二、复制书稿

Description

假设有M本书（编号为1，2，…M），想将每本复制一份，M本书的页数可能不同（分别是P1，P2，…PM）。任务是将这M本书分给K个抄写员（K〈=M〉，每本书只能分配给一个抄写员进行复制，而每个抄写员所分配到的书必须是连续顺序的。 意思是说，存在一个连续升序数列 0 = bo < b1 < b2 < … < bk-1 < bk = m，这样，第I号抄写员得到的书稿是从bi-1+1到第bi本书。复制工作是同时开始进行的，并且每个抄写员复制的速度都是一样的。所以，复制完所有书稿所需时间取决于分配得到最多工作的那个抄写员的复制时间。试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽可能小（如存在多个最优方案，输出结果排序最小的一种）

Input

第一行两个数m,k:表示书本数目与人数;第二行m个由空格分隔的整数,m本书每本的页数.(m<100)

Output

共k行。每行两个整数：第I行表示第I抄写员抄的书本编号起止。 Sample Input 9 3

1 2 3 4 5 6 7 8 9 Sample Output 1 5 6 7

8 9

【算法分析】

该题中 M 本书是顺序排列的，K 个抄写员选择数也是顺序且连续的。不管以书的编号，还是以抄写员标号作为参变量划分阶段，都符合策略的最优化原理和无后效性。考虑到K<=M，以抄写员编号来划分阶段会方便些。

设 F（I，J）为前 I 个抄写员复制前 J 本书的最小“页数最大数”。于是便有 F（I，J）=MIN{ F（I-1，V），T（V+1，J）} （1<=I<=K，I<=J<=M-K+I，I-1<=V<=J-1）。 其中 T（V+1，J）表示从第 V+1 本书到第 J 本书的页数和。边界条件 F（1,i）=T(1,j)。

题目类别：资源划分类

#include using namespace std; int a[100],b[100][100];

void out(int i,int j) { if(i==0) return;

out(i-1,b[i][j]-1);

cout<

int n,k,i,j,p,max,f[100][100],min,mp,x; cin>>n>>k;

a[0]=0;

for(i=1;i<=n;i++){ cin>>x;a[i]=a[i]+x;}//a[i]表示前i本书的页数累加和 for(i=1;i<=n;i++)

{f[1][i]=a[i];b[1][i]=1;} for(i=0;i<=k;i++) f[i][0]=0; for(i=2;i<=k;i++) for(j=1;j<=n-k+i;j++)

{ f[i][j]=200000;

for(p=i;p<=j;p++)//枚举第i个人抄的书的范围i?j { max=Max(f[i-1][p-1],a[j]-a[p-1]); if(f[i][j]>max)

{

f[i][j]=max;

b[i][j]=p;//前j本书由i个人抄时第i个人抄的第一本书编号为p } } } out(k,n); return 0; }

思考： 二分答案

【2001提高】统计单词个数1258

Description：给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(k小于等于40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。 Input：

第一行有二个正整数(p，k),p表示字串的行数;,k表示分为k个部分。 接下来的p行，每行均有20个字符。

再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6) 接下来的s行，每行均有一个单词。

Output ：结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。 Sample Input 1 3

thisisabookyouareaoh

4 is a ok sab

Sample Output：7

Hint：this/isabookyoua/reaoh

动归，题目中有一个非常特殊的地方，就是以串中某个位置的字母为首字母，最多只能分出一个单词。由于在拆分字符串的过程中，如果以某位置为首某个较短单词被截断，那么以该位置为首的较长单词必然也会被截断。也就是说，对于各个位置来说我们选取较短的单词总不会比选取较长的单词所形成的单词少。这样我们可以定义一个在位置

i的参数mlen[i]表示以位置i的字母为首字母，所能形成的最短单词的长度。这样如果在这个位置加上这个单词的长度之内截断，则以该位置为首字母就不能形成单词，否则就可能形成一个单词。这样对于所有的不同l个首位置，我们只要在各个位置依次对各个单词进行匹配就以得出所对应的mlen的值，这一部分的复杂度为O(wl2)。然后是计算把字串分为多个部分的过程中有什么单词可以留下。由于是把字串分为多个部分，故我们类比其他的分割字串的问题，列出动态规划的方程如下：

f[l,k]?max?f[l?i,k?1]?g[l?i?1,i]?

1?i?l?1这里有初值f[l,1]为： f[l,1]?g[1,l]

这个式子中，f[l,k]表示把字串前l个字符分成k段时所形成的最多单词的数目，

g[p,i]由于过于庞大，不能用预计算的方法加快速度，只能现用现算。计算的方法为对于所有

p?q?p?i?1的q，

如果mlen[q]存在（也就是有单词可以在位置q匹配上），且q单词。把所有这样位置的数目加起来就可以得到

?mlen[q]?1?p?i?1，则该位置必然可以匹配上一个

g[p,i]的值了。这样算法的复杂度为O(kl3)。

f的值。这样在i由i'增加到il增加，i增加的顺序计算但这里计算还有一个技巧，就是我们可以依次按照k增加，

的时候，由于在计算i'?1'?1所对应的g值时可以用

g[p?1,i'?1]?g[p,i']?1p?1?mlen[p?1]?1?p?i'?1

?g[p,i']p?1?mlen[p?1]?1?p?i'?1这个方程进行复杂度为O(1)的递推计算，故总复杂度可以降到O(kl2+wl2)。这种被称作双重动态规划的方法，请读者自己好好体会。 #include #include using namespace std; char s[200],b[6][10],g[100][100]; int f[1000][6]={0},n1; bool com(int x,int e,int j) { int i; for(i=0;ie||s[x+i]!=b[j][i])return false; return true; } int word(int x,int e) { int i,j,c=0; for(i=x;i<=e;i++) for(j=0;j>n>>k;n*=20; for(i=1;i<=n;i++)cin>>s[i]; cin>>n1; for(i=0;i>b[i]; for(i=1;i<=k;i++) for(j=i;j<=n-k+i;j++) { max=0; for(w=i-1;w<=j-1;w++) if(max

文件排版（format） Description

写电子邮件是有趣的，但不幸的是经常写不好看，主要是因为所有的行不一样长，你的上司想要发排版精美的电子邮件，你的任务是为他编写一个电子邮件排版程序。

完成这个任务最简单的办法是在太短的行中的单词之间插入空格，但这并不是最好的方法，考虑如下例子：

**************************** This is the example you are

actually considering.

假设我们想将第二行变得和第一行一样长，靠简单地插入空格则我们将得到如下结果： **************************** This is the example you are actually considering.

但这太难看了，因为在第二行中有一个非常大的空白，如果将第一行的单词“are”移到下一行我们将得到较好的结果：

**************************** This is the example you are actually considering.

当然，这必须对难看程度进行量化。因此我们必须给出单词之间的空格的难看程度，一个包含N个空格符的空白段，其难看程度值为(n-1)^2，程序的目的是使难看程度的总和最小化。例如，第一个例子的难看程度是1+7*7=50，而第二个例子的难看程度仅为1+1+1+4+1+4=12。

输出时，每一行的开头和结尾处都必须是一个单词，即每行开头和结尾处不能有空白。唯一例外的是该行仅有一个单词组成的情况，对于这种情况你可将单词放在该行开头处输出，此时如果该单词比该行应有的长度短则我们指定它的最坏程度为500，当然在这种情况下，该行的实际长度即为该单词的长度。 Input

输入文件第一行是一个整数N，表示该段要求达到的宽度，1<=N<=80。该段文章由一个或多个单词组成，单词由ASCII码值为33到126（包含33和126）的字符组成，单词与单词之间用空格隔开（可能超过一个）。单词长度不会超过段落要求达到的宽度。一段文字所有单词的总长度不会超过10000个字符，任何一行都不会超过100个字符，任何一个单词都在同一行内。 Output

对于每个段落，找出使其难看程度最小的排版形式并输出句子：“Minimal badness is B.”，B是指按可能的最好排版形式会发生的难看程度值。注意排版后文本行数任意，多余的空格也可删除。 Sample Input 28

This is the example you are actually considering. Sample Output

Minimal badness is 12.

思考：

筷子、乐队，邮局局问题、花的美学价值

合并类型DP(分治)

特点：一个大问题可由多个规模小的同类问题组合求解

【例题1】：最小代价子母树（石子归并问题）1119

Description

设有n堆石子排成一排，其编号为1、2、3、?、n（n<=100）。每堆石子的数量用：a[1]、a[2]、?、a[n] 表示，现将这n堆石子归并成一堆，归并的规则：

◆每次只能将相邻两堆归并成一堆，即：第 1 堆石子 a[1] 只能与第 2 堆石子 a[2] 归并，最后一堆石子 a[n] 只能与 a[n-1] 归并，中间的石子 a[i] 只能与 a[i-1] 或 a[i+1] 归并；

◆每次归并的代价是两堆石子的重量之和。

例如：假设有这样7堆石子，各堆石子的数量分别是：13 7 8 16 21 4 18，将它们归并成一堆有多种归并方法，下图表示了其中两种归并方法：

图a所示归并方式的总代价为：20+24+25+44+69+87=267 图b所示归并方式的总代价为：15+27+22+28+59+87=248 由此可见，不同的归并方式所得到的总代价是不一样的。那么当给出了n堆石子的数量之后，求出最小的总代价和最大的总代价。 Input

第一行一个整数 n，表示有 n 堆石子； 第二行有n个整数，表示每堆石子的个数； Output

第一行一个整数，表示合并的最小代价； 第二行一个整数，表示合并的最大代价； Sample Input 4

13 7 14 6 Sample Output

80 95 【算法分析】

（1）当N=2时，仅有一种堆法，因此总的归并代价为2堆沙子数量之和

（2）当N=3时，有2种堆法。从上图可看到它们总的代价分别为44和35。

（3）当N=4时，共有五种归并的方法，它们的总代价分别为94, 95, 80, 88, 87，最小的归并总代价为80（C）。

(A) (B) (C)

总代价=20+34+40=94 总代价=21+34+40=95 总代价=20+20+40=80

(D) (E)

总代价=21+27+40=88 总代价=20+27+40=8７

第一类包括（A），（B），基本方法是归并前面的三堆，再归并最后一堆，由于最后一堆归并的代价是相同的，所以在归并前面三堆时不同的方法将产生不同的结果。（A）的代价小于（B）的代价，因此（A）方法优。 第二类仅有一种方法（C），分别归并2堆的代价为２０，２０，相加为４０。 第三类包括（Ｄ），（Ｅ），基本方法是先归并后面三堆，再归并第一堆，由于最后一次归并代价是相同的，所以归并后三堆的方法不同将产生不同的结果。（Ｄ）的代价大于（Ｅ）的代价，因些方法（Ｅ）优。 引入数据结构：

1、F(i,j) 表示从i堆到j堆沙子归并的最小代价数。 如上讨论可知：

F(1,4)=MIN{ F(1,3), F(1,2)+F(3,4),F(2,4)}+40 而F(1,3)=min{F(1,2),F(2,3)}+34 F(1,2)=20 F(3,4)=20 F(2,3)=21

F(2,4)=MIN{F(2,3),F(3,4)}+27

2、g[i]：表示从第1堆到第i堆的石子的重量之和；

这样就有一般情况：

F(1,N)=MIN{ F(1,N-1), F(1,2)+F(3,N), F(1,3)+F(4,N), ……., F(2,N)}+G(N) G[i]：计算

for(i=1;i<=n;i++)g[i]=g[i-1]+a[i]; f[i][j]的计算过程：

如：

f(1,4)=min{f(1,3),f(1,2)+f(3,4),f(2,4)}+g(1,4) =min{43, 20+24, 46}+44 = 87

f(1,5)=min{f(1,4), f(1,2)+f(3,5),f(1,3)+f(4,5), f(2,5)}+g(1,5) =min{87 , 20+69, 43+37, 98}+65= 145 f(3,6)=min{f(3,5), f(3,4)+f(5,6),f(4,6)}+g(3,6)

=min{69, 24+25, 66}+49= 98

f(4,7)=min{f(4,6), f(4,5)+f(6,7),f(5,7)}+g(4,7)

=min{66, 37+22, 65}+59= 118

f(1,7)=min{f(1,6), f(1,2)+f(3,7), f(1,3)+f(4,7), f(1,4)+f(5,7), f(1,5)+f(6,7), f(2,7)}+g(1,7) =min{ 178, 20+156, 43+ 118, 87+ 65, 145+22, 185}+87=239 1、阶段和状态：设n堆石子的数量依次存储在a[1]、a[2]、?、a[n]中，由于本问题中只能是相邻两堆石子才能合并（与合并果子的区别），我们不妨设二维数组F，它的下标和值的含义分别为：

g[i]：表示从第1堆到第i堆的石子的重量之和；

fmin[i][j]:表示从第i堆到第j堆石子合并为一堆石子的最小代价; fmax[i][j]:表示从第i堆到第j堆石子合并为一堆石子的最大代价;

题目的阶段是：第几次合并t(1<=t<=n-1)，状态是：从第几堆开始合并石子i(1<=i<=n-t) 1、 状态转移方程：

f(1,n)=min{ f(1,n-1), f(1,2)+f(3,n), f(1,3)+f(4,n), ……., f(2,n)}+g(1,n) 初始化： g[i]=g[i-1]+a[i];fmax[i][i]=0; fmin[i][i]=0;

状态转移方程：fmin[i][j]=min{f[i][k]+f[k+1][j]+g[j]-g[i-1]}(i<=k<=j-1) 状态转移方程：fmax[i][j]=max{f[i][k]+f[k+1][j]+g[j]-g[i-1]}(i<=k<=j-1) Answer= fmin[1][n]和fmax[1][n] 3、核心子程序： void dp() { for(i=1;i<=n;i++)//计算g[i]的值

{ g[i]=g[i-1]+a[i]; fmax[i][i]=0; fmin[i][i]=0;} for(t=1;t<=n-1;t++)//阶段，第几次合并 for(i=1;i<=n-t;i++)//状态，合并的起始堆 { j=i+t; //合并的结束堆 fmin[i][j]=0x7fffffff; fmax[i][j]=0;//初始化 for(k=i;k<=j-1;k++) //决策，分界点 { fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]); fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]); } fmin[i][j]=fmin[i][j]+g[j]-g[i-1]; fmax[i][j]=fmax[i][j]+g[j]-g[i-1]; } } 4、完整的程序： #include using namespace std; int a[101],g[101],fmax[101][101],fmin[101][101],n,i,j,k,t; int minn(int x,int y) { if(x>n; for(i=1;i<=n;i++)cin>>a[i]; memset(g,0,sizeof(g)); memset(fmax,0,sizeof(fmax)); memset(fmin,0,sizeof(fmin)); dp(); cout<

#include using namespace std;

const int maxn=2005,MAX=~0u>>3;

int f[maxn][maxn]={0},s[maxn][maxn]={0},sum[maxn]={0},a[maxn],n,i; void init() {

cin>>n;

for(i=1;i<=n;i++){ cin>>a[i]; a[i+n]=a[i]; } for(i=1;i<=n*2;i++)sum[i]=sum[i-1]+a[i]; }

void dp() {

int j,k,l,ans;

for(i=1;i<=n*2;i++)s[i][i]=i; for( l=2;l<=n;l++)

for( i=1;i<=2*n-l+1;i++ ) {

j=i+l-1; f[i][j]=MAX;

for( k=s[i][j-1];k<=s[i+1][j];k++)//四边形不等式 if(f[i][j]>f[i][k-1]+f[k][j]) {

f[i][j]=f[i][k-1]+f[k][j]; s[i][j]=k; } f[i][j]+=sum[j]-sum[i-1]; } ans=MAX;

for(i=1;i<=n;i++)if(f[i][i+n-1]

for(i=1;i<=2*n-l+1;i++) {

j=i+l-1;

//最大只来源于两种情况：i+(i+1?j)或(i?j-1)+j if(f[i][j-1]>f[i+1][j])f[i][j]=f[i][j-1]+sum[j]-sum[i-1]; else f[i][j]=f[i+1][j]+sum[j]-sum[i-1]; }

ans=0;

for(i=1;i<=n;i++)if(f[i][i+n-1]>ans)ans=f[i][i+n-1]; cout<

【例题】添加括号1688

【题目背景】给定一个正整数序列a(1)，a(2)，...，a(n),(1<=n<=20)，不改变序列中每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。 例如：给出序列是4,1,2,3。

第一种添括号方法：((4+1)+(2+3))=((5)+(5))=(10) 有三个中间和是5,5,10,它们之和为：5+5+10=20

第二种添括号方法：(4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10) 中间和是3,6,10,它们之和为19。

【问题描述】现在要添上n-1对括号，加法运算依括号顺序进行，得到n-1个中间和，求出使中间和之和最小的添括号方法。

【文件输入】文件输入共两行。第一行为整数n (1<=n<=20)。第二行为a(1),a(2),...,a(n)这n个正整数，每个数字不超过100。 【文件输出】文件输出共3行。第一行为添加括号的方法。第二行为最终的中间和之和。第三行为n-1个中间和，按照从里到外，从左到右的顺序输出。 【样例输入】 【样例输出】 4 (4+((1+2)+3)) 4 1 2 3 19 3 6 10 【思路点拨】 f[i][j]：表示从i开始到第j个数合并为一个数所得到的最小和。 f[i][j]=min{f[i][k]+f[k+1][j]+sum[i][j]} sum[i][j]：表示从i到j之间的和。 #include using namespace std;

long a[21]={0},s[21]={0},f[21][21]={0},v[21][21]={0},s1=0; void out(long t,long w)

{ if(t==w){cout<

cout<<'+';out(v[t][w]+1,w);cout<<')'; }

long jia(long t,long w) { long x=0,y=0;

if(t==w)return a[t];

if(t==v[t][w]&&v[t][w]+1==w)

{cout<

if(t<=v[t][w])x=jia(t,v[t][w]);

if(v[t][w]+1<=w)y=jia(v[t][w]+1,w); cout<

int main()

{ long n,i,j,k,t,min; cin>>n;

for(i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];} for(i=n-1;i>0;i--)

for(j=i+1;j<=n;j++) { min=99999999; for(k=i;k

if(f[i][k]+f[k+1][j]

out(1,n);

cout<

【例题】：矩阵相乘1645

Description

在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个m行、n列的矩阵（简称m×n的矩阵），B是一个n行、p列的矩阵（简称n×p的矩阵），则其乘积C=A×B是一个m×p的矩阵。其标准计算公式为：

由该公式知计算C=A×B总共需要进行m×n×p次的数乘法，我们将两个矩阵乘法次数定义为矩阵想乘的时间复杂度。 矩阵乘法满足矩阵乘法满足结合律（但不满足交换律），即对于D=A×B×C，可以有如下两种计算方式： 1、D=（A×B）×C 2、D=A×（B×C）

假设A是个10×100的矩阵、B是个100×5的矩阵，C是个5×50的矩阵，那么： ●按照第一种计算方法得到的时间复杂度是：10×100×5+10×5×50=7500； ●按照第一种计算方法得到的时间复杂度是：100×5×50+10×100×50=75000；

所以不同的计算顺序得到的时间复杂度是不一样的，现在的问题是：顺序给出n个矩阵的大小，请计算出它们的乘积的最小的时间复杂度。 Input

第一行输入一个正整数n，表示有n个矩阵。

接下来m行每行两个正整数Xi，Yi，其中第i行的两个数表示第i个矩阵的规模为Xi行、Yi列。所有的Xi、Yi<=100。 输入数据保证这些矩阵可以相乘。 Output:n个矩阵连乘最小时间复杂度。 Sample Input 3

10 100 100 5 5 50

Sample Output:7500 数据范围：n<=100。

【例题】能量项链1511

【问题描述】在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘(吸盘是Mars人吸收能量的一种器官)的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r,尾标记为n，则聚合后释放的能量为m*r*n(Mars单位)，新产生的珠子的头标记为m，尾标记为n。

需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。

例如：设N=4,4颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：

(4⊕1)=10*2*3=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。

【输入文件】输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

9

【输出文件】输出文件energy.out只有一行，是一个正整数E（E≤2.1*10），为一个最优聚合顺序所释放的总能量。 【输入样例】 4

2 3 5 10

【输出样例】710 【思路点拨】

环形问题解决思路：

1、 枚举断开点，使用n次DP找最优 2、 将长为n的环展开成(2*n-1)长的链，其中n后的部份复制1?n-1,子问题规模最大求到n,一次DP后输出n个规模为n

的子问题中最好的

设f[i][j]表示将从第i个珠子聚合到第j个珠子的最大释放能量。假设最后合并的位置为k和k+1，则： f[i][j]=max{f[i][k]+f[k+1][j]+a[i]*b[k]*b[j]},1<=i<=k<=j<=n 初始化：f[i][i]=0;

ans=max{f[1][n],f[2][n+1]….+f[n][2n-1]} #include using namespace std;

int a[205],b[205],f[205][205]; int main()

{ int ans=0,n,i,L,s,t; cin>>n;

for(i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}// 环展开成链 for(i=1;i<=2*n-1;i++)b[i]=a[i+1]; b[2*n]=a[1];

for(L=2;L<=n;L++)//规模最大求到n for(s=1;s<=2*n-L+1;s++) { t=s+L-1; f[s][t]=0;

for(i=s;i<=t-1;i++)

f[s][t]=maxx(f[s][t],f[s][i]+f[i+1][t]+a[s]*b[i]*b[t]); }

for(i=1;i<=n;i++)ans=maxx(ans,f[i][i+n-1]);// n个规模为n的子问题中最好的 cout<

【例题】多边形游戏2251

【问题描述】多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点组成的多边形。每个顶点赋予一个整数（不超过整型范围），每条边赋予一个运算符号“+”或“*”。所有的边按顺时针从0---n-1编号。在游戏的第一步，删除一条边，随后的n-1步按如下方式操作：

（1）选择一条边E及由E相连的顶点V1，V2;

（2）用一个新的顶点替代E及V1,V2，新顶点为v1与V2采用E的运算所得值。 当所有边被删除时游戏结束。游戏的得分就是最且那个顶点的值。

问题：对于给定的多边形，计算其最高得分。

【文件输入】第1行为一个整数N (1<=N<=50), 表示顶点数；第2行为一串字符表示顶点及边的序列如1+3*2*5+，该序列肯定正确,不必验证。

【文件输出】文件输出只有一行，表示最高得分。 【样例输入】 3

2+3*2+

【样例输出】12

【数据范围】70%数据数据运算过程中不超过long范围 30%数据数据运算过程中超过long范围

【思路点拨】这是一道环形合并问题，主要思想同石子合并或能量项链，但要注意几点，由于顶点为整数，没有说明正整数，因此可能为负数，所以在处理过程中，要保留两个状态，即将从i点到j点合并成一点时的最大值和最小值，因为两个负数的最小乘起来可能最大。关于高精度问题，最好用封装的处理。

#include #include using namespace std;

double f[101][101],g[101][101],max; int a[51],b[51],i,n,x; char c;bool tt;

double work(double x,double y,int t) { if(t==0)return x+y; if(t==1)return x*y; }

void dp()

{ int i,j,k;double temp; for(i=n-1;i>=1;i--) for(j=i+1;j<=n;j++) if(j-i<=(n+1)/2)

{ f[i][j]=-1e100; g[i][j]=1e100; for(k=i;k<=j-1;k++)

{ temp=work(f[i][k],f[k+1][j],b[k]); if(f[i][j]temp)g[i][j]=temp;

temp=work(f[i][k],g[k+1][j],b[k]); if(f[i][j]temp)g[i][j]=temp;

temp=work(g[i][k],f[k+1][j],b[k]); if(f[i][j]temp)g[i][j]=temp;

temp=work(g[i][k],g[k+1][j],b[k]); if(f[i][j]temp)g[i][j]=temp; } } }

int main()

{ cin>>n;i=0; while(i

{ i++;x=0;tt=false; do{ cin>>c;

if(c=='-'){tt=true;cin>>c;}

if(c>='0'&&c<='9')x=x*10+(c-'0'); }while(c>='0'&&c<='9'); a[i]=x;if(tt)a[i]=-x;

if(c=='+')b[i]=0;else b[i]=1; }

for(i=1;i<=n;i++)f[i][i]=a[i];

for(i=n+1;i<=2*n-1;i++){f[i][i]=a[i-n];b[i]=b[i-n];} for(i=0;i<=100;i++)

for(int j=0;j<=100;j++)g[i][j]=f[i][j]; n=2*n-1;double max=-1e100; dp();

n=(n+1)/2;

for(i=1;i<=n;i++)if(max

【例题】凸多边形的划分1981

【问题描述】给定一个具有N(N<50)个顶点(从1到N编号)的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？ 【输入文件】第一行为顶点数N;第二行为N个顶点(从1到N)的权值。 【输出格式】最小的和的值。 【输入示例】 5

122 123 245 231 【输出示例】12214884

【思路点拨】首先，这是一个剖分问题，那么是否可以用我们上述所说的合并类动态规划解决呢？

我们知道，对于任意一个凸多边形，如果我们从中去掉任意一个三角形后，可以变成三块，其中两块仍然为凸多边形，另一个为三角形。

设f[i][j](i

但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算。 #include #include using namespace std;

typedef long long array[60]; array F[110][110],a,s1,s2,s3; long long n;

void mark(array &c)

{ for(int i=1;i<=c[0];i++) {c[i+1]+=c[i]/100000;c[i]%=100000;}

while (c[c[0]+1])

{ c[0]++;c[c[0]+1]+=c[c[0]]/100000;c[c[0]]%=100000;} }

void mul(long long a1,long long a2,long long a3,array &c) { memset(c,0,sizeof(c));c[0]=c[1]=1; for(int i=1;i<=c[0];i++)c[i]*=a1; mark(c);

for(int i=1;i<=c[0];i++)c[i]*=a2; mark(c);

for(int i=1;i<=c[0];i++)c[i]*=a3; mark(c); }

void add(array a,array b,array &c) { memset(c,0,sizeof(c));

if(a[0]>b[0])c[0]=a[0];else c[0]=b[0]; for(int i=1;i<=c[0];i++)c[i]=a[i]+b[i]; mark(c); }

bool check(array a,array b) { if(a[0]b[0])return true; for(int i=a[0];i>=1;i--)

if(a[i]b[i])return true; return false; }

int main()

{ scanf(\

for(int i=1;i<=n;i++)scanf(\ for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)F[i][j][0]=1; for(int i=n-2;i>=1;i--) for(int j=i+2;j<=n;j++) { F[i][j][0]=60; for(int k=i+1;k<=j-1;k++) { mul(a[i],a[k],a[j],s1); add(F[i][k],F[k][j],s2); add(s1,s2,s3); if(check(F[i][j],s3))memcpy(F[i][j],s3,sizeof(F[i][j])); } }

printf(\

for(int i=F[1][n][0]-1;i>=1;i--)printf(\ printf(\}

思考：

最少正方形bsoi2973

LCS类型DP

【培训练习题】最长公共子序列1598

Description

一个给定的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 X = < X1，X2，…，Xm >，则另一序列Z = < Z1，Z2，…，Zk > 是x的子序列是指存在一个严格递增的下标序列< i1，i2，…，ik >，使得对于所有 j=1，2，…，k 有：

例如，序列Z=< B，C，D，B >是序列X=< A，B，C，B，D，A，B >的子序列，相应的递增下标序列为< 2，3，5，7 >。给定两个子序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

在例如，若X=< A，B，C，B，D，A，B >和Y=< B，D，C，A，B，A >，则序列< B，C，A >是X和Y的一个公共子序列，序列< B，C，B，A >也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有一个长度大于4的公共子序列。

给定两个序列X = < X1，X2，…，Xm >和 Y = < Y1，Y2，…，Ym >，要找出X和Y的一个最长公共子序列。 Input

共有两行，每一行为一个大写字母构成的长度不超过2000的字符串，表示序列X和Y。

Output

一个非负正整数，表示所求得的最长公共子序列的长度，若不存在公共子序列，则文件仅有一行输出一个整数0。 Sample Input ABCBDAB BDCABA Sample Output 4 【算法分析】 1、阶段和状态：

设二维数组F，其下标和值的含义为：

F[i][j]=x 表示字符串S1的前i个字符与字符串S2的前j个字符的最长公共子串长度为x。

2、状态转移方程： 由上面的叙述可知：

F[i?1，j?1]?1? F[i,j]?max??Max{F[i?1，j]，F[i,j?1]}如果s[i]?p[j](如果s[i]??p[j])

3、核心子程序： int main() { memset(f,0,sizeof(f)); cin>>s1>>s2; l1=s1.length();l2=s2.length(); s1=' '+s1;s2=' '+s2; for(i=1;i<=l1;i++) for(j=1;j<=l2;j++) if(s1[i]==s2[j])f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); cout<

【培训试题】编辑距离1374

Description

设A和B是两个字符串。我们用最少的字符操作，将字符串A转换为字符串B。这里所说的字符操作包括： (1)删除一个字符； (2)插入一个字符；

(3)将一个字符改为另一个字符。

将字符串A转换为字符串B所用的最少字符操作数称为字符串A到字符串B的编辑距离，记为δ(A，B)。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离δ(A，B)。

Input:两行，每行代表一个字符串（串长小于200） Output:一个数，代表两者的最小编辑距离 Sample Input

ab ac

Sample Output:

1 【试题分析】 1、阶段和状态：

f[i][j]：表示将A的前i个字符变成B的前j个字符的最少操作次数 求f[i][j]要考虑3种操作：

(1).在A中删除一个字符：f[i-1][j] (2).在A中插入一个字符：f[i][j-1]

(3).在A中将一个字符改为另一个字符，如果a[i]=b[i]为f[i-1][j-1],如果a[i]!=b[i]为f[i-1][j-1]+1。 2、状态转移方程：

f[i][j]=min{f[i-1][j-1](a[i]=b[i]);min{f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+1}} 初始化：f[0][i]=f[i][0]=i; answer=f[a1][b1]

3、核心子程序： cin>>s1>>s2; l1=s1.length();l2=s2.length(); for(i=l1;i>0;i--) s1[i]=s1[i-1];//s1=’ ’+s1; for(i=l2;i>0;i--) s2[i]=s2[i-1]; memset(f,0,sizeof(f)); for(i=1;i<=l1;i++) f[i][0]=i; for(i=1;i<=l2;i++) f[0][i]=i; for(i=1;i<=l1;i++) for(j=1;j<=l2;j++) if(s1[i]==s2[j]) f[i][j]=f[i-1][j-1]; else f[i][j]=min(f[i-1][j-1]+1,min(f[i-1][j]+1,f[i][j-1]+1)); cout<

Description

回文词是一种对称的字符串——也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的

任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。 Input

第一行包含一个整数N，表示给定字符串的长度（3≤N≤50 00）。

第二行是一个长度为N的字符串。字符串仅由大写字母“A”到“Z”，小写字母“a”到“z”和数字“0”到“9”构成。大写字母和小写字母将被认为是不同的。 Output

只有一行，包含一个整数，表示需要插入的最少字符数。 Sample Input 5

Ab3bd Sample Output 2 【试题分析】 1、阶段和状态：

设f(i,j)表示使得S的[1..i]和[j..n]部分构成回文需要添加的最少字母个数 。 2、状态转移方程： f(i-1,j)+1, f(i,j)=min f(i,j+1)+1, f(i-1, j+1), S(i)=S(j) 边界为f(0,n+1)=0 Ans=min{f(i, i), f(i,i+1)}

3、核心子程序： int f[5005][5005]={0};string s; int main() { long n,i,j,ans; cin>>n>>s;s=' '+s; for(i=1;i<=n;i++){f[0][i]=n-i+1;f[i][n+1]=i;} for(i=1;i<=n;i++) for(j=n;j>=i;j--) if(s[i]==s[j])f[i][j]=f[i-1][j+1]; else f[i][j]=min(f[i-1][j],f[i][j+1])+1; ans=9999999; for(i=0;i<=n;i++) { if(f[i][i+1]0&&f[i][i]

本文来源：https://www.bwwdw.com/article/u4x5.html