DP类型各题总结-acm.doc

最大连续子序列Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 11540Accepted Submission(s): 4856还需要输出该子序列的第一个和最后一个元素。对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元 素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。 思路：一路加 如果sum变成小于0了 从当前位置重新新开始加（小于0的话 就对整个段没有贡献了 而且会使整个段的和变小）#includeint main() int n,i,a10005,start,end,sum,max,sta,flag,cnt; while(1) cnt=0; sum=0;max=-1;flag=1; scanf(%d,&n); if(n=0) return 0; for(i=0;in;i+) scanf(%d,&ai); if(ai0) cnt+; if(ai=0) flag=0; start=sta=end=a0; if(cnt=n|cnt=n-1) if(flag=0) printf(0 0 0n); continue; else if(n!=1) printf(0 %d %dn,a0,an-1);continue; for(i=0;in;i+) sum=sum+ai; if(sum0&i+1max) max=sum; end=ai;start=sta; printf(%d %d %dn,max,start,end); Hdu 1087 super jumping 题意：此题就是找序列中最大升序子序列的和。可跳 不一定非要连续比如 1 3 2 中升序序列有：1321，31，2。所以最大为1+3=4；#include_int64 a1005,sum1005;int main() int i,j,n,max,ans; while(scanf(%d,&n)&n) for(i=0;in;i+) scanf(%I64d,&ai);sumi=ai; ans=0; for(i=0;in;i+)/j比i小 for(j=0;ji;j+) if(aj(sumj+ai)?sumi:(sumj+ai);/sumj 之前已经求出来了 ans=anssumi?ans:sumi; printf(%dn,ans); return 0; Common Subsequence Time Limit : 2000/1000ms (Java/Other)Memory Limit : 65536/32768K (Java/Other)Total Submission(s) : 29Accepted Submission(s) : 16Problem DescriptionA subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = another sequence Z = is a subsequence of X if there exists a strictly increasing sequence of indices of X such that for all j = 1,2,.,k, xij = zj. For example, Z = is a subsequence of X = with index sequence . Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y. The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line. Sample Inputabcfbc abfcabprogramming contest abcd mnpSample Output420题意：求两个串的最长公共子序列用f i j 表示处理到字符串A的第 i 位 和 字符串B第 j 位时的最大值。状态转移方程如下：f i j = f i - 1 j - 1 + 1 (A i = B j )f i j = max( f i - 1 j , f i j - 1 ) (A i != B j )由于每次循环计算只和上一行状态有关，所以可以用循环数组压缩空间和背包中的一样哦#include#includechar a1000,b1000;int dp10001000;int d1,d2;int main() int i,j; while(scanf(%s,a+1)!=EOF) scanf(%s,b+1); d1=strlen(a+1); d2=strlen(b+1); for(i=0;i=d1;i+) dpi0=0; for(j=0;j=d2;j+) dp0j=0; for(i=1;i=d1;i+) for(j=1;jdpij-1?dpi-1j:dpij-1; printf(%dn,dpd1d2); return 0;很好的hdu 1080 Human Gene Functions输入2 7 AGTGATG 5 GTTAG 7 AGCTATT 9 AGCTTTAAA 输出14 21题意：两个字符串，每个字符串中都可以插入-，保证最后两串的长度相等，之后让两串对齐，两串相同位置的字母组成的字符匹配有一个值，问这些值的和最大是多少，是第一题的变形下图为字符匹配所得价值的表dpij表示0到i-1跟0到j-1配对的最大价值状态转移：dpij由dpi-1j转移过来，代价是ai-1跟-匹配由dpij-1转移过来，代价是bj-1跟-匹配由dpi-1j-1转移过来，代价是ai-1跟bj-1匹配、#include#includeint max500500;int map150150;void match() mapAA=5;mapAC=-1;mapAG=-2;mapAT=-1;mapA-=-3; mapCA=-1;mapCC=5;mapCG=-3;mapCT=-2;mapC-=-4; mapGA=-2;mapGC=-3;mapGG=5;mapGT=-2;mapG-=-2; mapTA=-1;mapTC=-2;mapTG=-2;mapTT=5;mapT-=-1; map-A=-3;map-C=-4;map-G=-2;map-T=-1;/map-=-3;int main() int i,j,t,len1,len2; char q1500,q2500; match(); scanf(%d,&t); while(t-) scanf(%d %s,&len1,q1+1); scanf(%d %s,&len2,q2+1); memset(max,0,sizeof(max); max00=0; for(i=1;i=len1;i+) /maxi0=mapq1i-;/哎 这里初始化搞错了 阿弥陀佛 maxi0=maxi-10+mapq1i-; for(j=1;j=len2;j+) / max0j=map-q2j; max0j=max0j-1+map-q2j; for(i=1;i=len1;i+) for(j=1;j(maxi-1j+mapq1i-)? (maxi-1j-1+mapq1iq2j):(maxi-1j+mapq1i-); maxij=maxij(maxij-1+map-q2j)?maxij:(maxij-1+map-q2j); printf(%dn,maxlen1len2); return 0;Hdu 2084 有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 = N = 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间0,99内。Output对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。Sample Input1573 88 1 0 2 7 4 44 5 2 6 5Sample Output30#includeint a105105;int dp105105;int main() int i,j,n,t; scanf(%d,&t); while(t-) scanf(%d,&n); for(i=1;i=n;i+) for(j=1;j=i;j+) scanf(%d,&aij); for(j=1;j=1;i-) for(j=1;jdpi+1j+1?dpi+1j:dpi+1j+1); printf(%dn,dp11); return 0; SGU104 Little Shop of Flowers (DP) 分类： SGU DP 2012-04-08 22:54 107人阅读 评论(0) 收藏 举报 动态规划题用dpij表示把前i束花放在前j个花瓶里所得到的最大的美观值(i=j)。递推式为：dpij = max(dpij-1, dpi-1j-1 + Aij)，dpFV即为所求。题目还要求输出每束花的摆放位置，可以用preij=0或1表示dpij是由dpij-1或dpi-1j-1 + Aij得来的，然后递归输出结果，具体看代码中的print(int, int)函数。#include #include #include #include #include using namespace std;const int maxn = 110;int f, v;int amaxnmaxn, dpmaxnmaxn;int premaxnmaxn;int DP() dp00 = 0; for (int i = 1; i = f; +i) dpii-1 = -100000; for (int i = 1; i = f; +i) for (int j = i; j dpi-1j-1 + aij) dpij = dpij-1; preij = 0; else dpij = dpi-1j-1 + aij; preij = 1; return dpfv; void print(int i, int j) if (j = 0) return ; if (preij = 1) print(i - 1, j - 1); if (i = f) printf(%dn, j); else printf(%d , j); else print(i, j - 1); int main() while (scanf(%d %d, &f, &v) != EOF) for (int i = 1; i = f; +i) for (int j = 1; j = v; +j) scanf(%d, &aij); printf(%dn, DP(); print(f, v); return 0;Max Sum Time Limit : 2000/1000ms (Java/Other)Memory Limit : 65536/32768K (Java/Other)Total Submission(s) : 104Accepted Submission(s) : 31Problem DescriptionGiven a sequence a1,a2,a3.an, your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.InputThe first line of the input contains an integer T(1=T=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1=N=100000), then N integers followed(all the integers are between -1000 and 1000).OutputFor each test case, you should output two lines. The first line is Case #:, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.Sample Input25 6 -1 5 4 -77 0 6 -1 1 -6 7 -5Sample OutputCase 1:14 1 4Case 2:7 1 6#includeint a100010;int main() int n,i,start,end,sum,max,sta,ti,k;scanf(%d,&ti);for(k=1;k=ti;k+)sum=0;max=-1111;scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&ai);start=sta=end=1;for(i=1;imax)/这个if要放在下面的if语句的上面 max=sum;end=i;start=sta;if(sum micei.speed + 1, 最后找出最大的fi即可。注意此题还需要输出找到的序列中的老鼠的最原始的标号，因此不仅要在刚开始的时候把每个老鼠的最初的序号记下来，还要在进行状态转移的时候把当前的老鼠的位置标记下来。#include#include#includestruct haha int wei; int spe; int num;a1010;int cmp(const void *a,const void *b) if(*(struct haha *)a).wei!=(*(struct haha *)b).wei) return (*(struct haha *)a).wei-(*(struct haha *)b).wei; else return (*(struct haha *)b).spe-(*(struct haha *)a).spe;int l1010,pre1010,ans1010;/l是记录的长度 pre记录的是路径int main() int cnt=1,i,j,max_l=0,end; while(scanf(%d %d,&acnt.wei,&acnt.spe)!=EOF) acnt.num=cnt+; qsort(a+1,cnt-1,sizeof(struct haha),cmp); for(i=1;icnt;i+) li=1;prei=0; for(i=1;icnt;i+) for(j=1;jaj.wei&ai.speaj.spe&lilj+1) li=lj+1; prei=j;/这里面记录的是倒序 后面要倒着输出 end=1; max_l=l1; for(i=2;icnt;i+) if(max_lli) max_l=li;end=i; printf(%dn,max_l); for(i=1;i=1;i-) printf(%dn,aansi.num); return 0; To The Max Time Limit : 2000/1000ms (Java/Other)Memory Limit : 65536/32768K (Java/Other)Total Submission(s) : 30Accepted Submission(s) : 16Problem DescriptionGiven a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.As an example, the maximal sub-rectangle of the array:0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2is in the lower left corner:9 2-4 1-1 8and has a sum of 15.InputThe input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range -127,127.OutputOutput the sum of the maximal sub-rectangle.Sample Input40 -2 -7 0 9 2 -6 2-4 1 -4 1 -18 0 -2Sample Output15/*题目大意：给定一个含有正数和负数的矩阵，求其子矩阵的和的最大值一维的情况很简单，如何把一维的情况转化为二维情况呢？例如，对于本题的测试数据：我们可以每次任选几行，压缩成一行，这样就转化为了一维情况。例如，我们求12行中的最大子矩阵：即矩阵高为2（12行），宽为1：4的矩阵，可以先把12行相加，得到9 0 -13 2，再求这个单行的最大子段，由此就可以求得12行的最大子矩阵。*/#include#includeint max,n;int map105105,b105;int dp()int i,sum=0,m=-1000;for(i=0;in;i+)sum=sum+bi;if(summ) m=sum;return m;int main()int i,j,k,t,ans;while(scanf(%d,&n)!=EOF)for(i=0;in;i+)for(j=0;jn;j+)scanf(%d,&mapij); max=0;/一开始没有初始化 没法和后面的比较大小啊 所以WA了 所以要注意也谢细节问题for(i=0;in;i+)/从第几行开始for(k=0;kn;k+)/行数if(i+kn)memset(b,0,sizeof(b);for(t=i;t=i+k;t+)for(j=0;jans?max:ans;printf(%dn,max);return 0;Advanced FruitsTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 877Accepted Submission(s): 407Special JudgeProblem DescriptionThe company 21st Century Fruits has specialized in creating new sorts of fruits by transferring genes from one fruit into the genome of another one. Most times this method doesnt work, but sometimes, in very rare cases, a new fruit emerges that tastes like a mixture between both of them. A big topic of discussion inside the company is How should the new creations be called? A mixture between an apple and a pear could be called an apple-pear, of course, but this doesnt sound very interesting. The boss finally decides to use the shortest string that contains both names of the original fruits as sub-strings as the new name. For instance, applear contains apple and pear (APPLEar and apPlEAR), and there is no shorter string that has the same property. A combination of a cranberry and a boysenberry would therefore be called a boysecranberry or a craboysenberry, for example. Your job is to write a program that computes such a shortest name for a combination of two given fruits. Your algorithm should be efficient, otherwise it is unlikely that it will execute in the alloted time for long fruit names. InputEach line of the input contains two strings that represent the names of the fruits that should be combined. All names have a maximum length of 100 and only consist of alphabetic characters.Input is terminated by end of file. OutputFor each test case, output the shortest name of the resulting fruit on one line. If more than one shortest name is possible, any one is acceptable.Sample Inputapple peachananas bananapear peachSample Outputappleachbananaspearchhdu ： /showproblem.php?pid=1503题意：两种水果杂交出一种新水果，现在给新水果取名，要求这个名字中包含了以前两种水果名字的字母，并且这个名字要尽量短。也就是说以前的一种水果名字arr1是新水果名字arr的子序列，另一种水果名字arr2也是新水果名字arr的子序列。要你求arr。做法：用求最长公共子序列的方法，求出arr1和arr2的最长公共子序列，然后再用递归思想，逐一输出，得到的就是最后答案。#include #include #define size 201 int Max(int x,int y) return xy?x:y; struct rem int i,j;/*i记录主串位置，j记录副串当前字符位置*/ char ch;/*记录当前字符*/ ; char asize,bsize; int dpsizesize; rem anssize; int len;/*指示ans的长度*/ void lcs(int m,int n) int i,j; memset(dp,0,sizeof(dp); len = 0; for (i=1;i=m;i+) for (j=1;jdpij-1) i-; else j-; /*取出最长公共子序列的字母*/ int main() int a1,b1,i,j,k; while (scanf(%s%s,a+1,b+1)!=EOF) a1 = strlen(a+1); b1 = strlen(b+1); lcs(a1,b1); i = j = 1; for (k=len-1;k=0;k-) while (i!=ansk.i) printf(%c,ai); i+; while (j!=ansk.j) printf(%c,bj); j+; printf(%c,ansk.ch); i+,j+; printf(%s%sn,a+ans0.i+1,b+ans0.j+1); return 0; /*Largest Rectangle in a HistogramTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5411Accepted Submission(s): 1545Problem DescriptionA histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths