动态规划入门(2)

1、动态规划入门（2）问题引入： X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，共n辆车，按照编号先后发车，夹在其它车流中，缓缓前行。 路边有个死胡同，只能容一辆车通过，是临时的检查站，如图【p1.png】所示。 X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。 如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？ dp(i,j)=dp(i-1,j+1)+dp(i,j-1)问题引入（2）:ABC每个字母有每个字母有n个，求满足要求的排列的个数：在该个，求满足要求的排列的个数：在该排列的任意前缀中满足排列的任意前缀中满足

2、 A的个数不少于的个数不少于B的的个数个数, B的个的个数数不不少于少于C的个数。的个数。dpijk = dpi-1jk+dpij-1k+dpijk-1，并且，并且i=j=k在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f（6）=14。h(n)= h(0)*h(n-1)+h(1)*h(n-2) + . + h(n-1)h(0) (n=2)算出1题和3题的部分答案 第一题 125134213242914301679658786。 第三题1251342132429143016796587

3、86。卡特兰数状态转移的相关内容 问题 hdu2191悼念悼念512汶川大地震遇难同胞汶川大地震遇难同胞珍惜现在，感恩生活珍惜现在，感恩生活为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。请问：你用有限的资金最多能采购多少公斤粮食呢？Input输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1=n=100, 1=m=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1=p=20,1=h=200,1=c=2

4、0)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。Output对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。两种状态转移方程 dpj=max(dpj,dpj-pi+vi); dpj=max(dpj,dpj-pi*k+k*vi);dpi数组的意义为容量为i时的最大价值#include #include #include using namespace std;int main() int n,m,dp105,kase,num105,v105,p105; scanf(%d,&kase); while( kase

5、-) scanf(%d%d,&n,&m); for(int i=0; im; i+) scanf(%d%d%d,&pi,&vi,&numi); memset(dp,0,sizeof(dp); for(int i=0; i0; j-) for(int k=1; k=0) dpj=max(dpj,dpj-pi*k+k*vi); printf(%dn,dpn); return 0;#include #include #include using namespace std;int main() int n,m,dp105,kase,num105,v105,p105; scanf(%d,&kase);

6、 while( kase-) scanf(%d%d,&n,&m); for(int i=0; im; i+) scanf(%d%d%d,&pi,&vi,&numi); memset(dp,0,sizeof(dp); for(int i=0; im; i+) for(int k=1; k0; j-) if(j-pi=0) dpj=max(dpj,dpj-pi+vi); printf(%dn,dpn); return 0;Floyd算法 void Floyd() int i,j,k; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(distik

7、+distkjdistij) distij=distik+distkj; 那么，就有：1.若最短路径经过节点vk，则D(i,j,k) = D(i,k,k-1) + D(k,j,k-1)； 2.若最短路径不经过节点vk，则D(i,j,k) = D(i,j,k-1)。所以，求的vi到vj的最短路径可表示为：D(i,j,k) = min（D(i,k,k-1) + D(k,j,k-1), D(i,j,k-1)）。最短距离有三种情况：、两点的直达距离最短。（如下图）、两点间只通过一个中间点而距离最短。（图）、两点间用通过两各以上的顶点而距离最短。（图）对于第二种情况：弗洛伊德算法的基本操作就是对于每一对

8、顶点，遍历所有其它顶点，看看可否通过这一个顶点让这对顶点距离更短，也就是遍历了图中所有的三角形（算法中对同一个三角形扫描了九次，原则上只用扫描三次即可，但要加入判断，效率更低）。对于第三种情况：如下图的五边形，可先找一点（比如x，使=2），就变成了四边形问题，再找一点（比如y,使=2），可变成三角形问题了（v,u,w），也就变成第二种情况了，由此对于n边形也可以一步步转化成四边形三角形问题。（这里面不用担心哪个点要先找哪个点要后找，因为找了任一个点都可以使其变成（n1）边形的问题）。课后练习n个人（编号0(n-1)，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。int JosephusPr