DP类型各题总结-acm

1、 11/11DP类型各题总结-acm 最大连续子序列 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 11540 Accepted Submission(s): 4856 还需要输出该子序列的第一个和最后一个元素。 对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元 素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列

2、的首尾元素。 思路：一路加如果sum变成小于0了从当前位置重新新开始加（小于0的话就对整个段没有贡献了而且会使整个段的和变小） #include int main() int n,i,a10005,start,end,sum,max,sta,flag,cnt; while(1) cnt=0; sum=0;max=-1;flag=1; scanf(%d, if(n=0) return 0; for(i=0;imax) max=sum; end=ai;start=sta; printf(%d %d %dn,max,start,end); Hdu 1087 super jumping 题意：此题就是

3、找序列中最大升序子序列的和。 可跳不一定非要连续 比如 1 3 2 中升序序列有：1321，31，2。所以最大为1+3=4； #include _int64 a1005,sum1005; int main() int i,j,n,max,ans; while(scanf(%d,isumi?ans:sumi; printf(%dn,ans); return 0; Common Subsequence Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other) Total Submission(s)

4、: 29 Accepted Submission(s) : 16 Problem Description A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = #include char a1000,b1000; int dp10001000; int d1,d2; int main() int i,j; while(scanf(%s,a+1)!=EOF) scanf(%s,b+1); d1=strlen(

5、a+1); d2=strlen(b+1); for(i=0;idpij-1?dpi-1j:dpij-1; printf(%dn,dpd1d2); return 0; 很好的hdu 1080 Human Gene Functions 输入 2 7 AGTGA TG 5 GTTAG 7 AGCTA TT 9 AGCTTTAAA 输出 14 21 题意：两个字符串，每个字符串中都可以插入-，保证最后两串的长度相等，之后让两串对齐，两串相同位置的字母组成的字符匹配有一个值，问这些值的和最大是多少，是第一题的变形 下图为字符匹配所得价值的表 dpij表示0到i-1跟0到j-1配对的最大价值 状态转移：

6、dpij由dpi-1j转移过来，代价是ai-1跟-匹配 由dpij-1转移过来，代价是bj-1跟-匹配 由dpi-1j-1转移过来，代价是ai-1跟bj-1匹配 、#include #include int 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;mapT

7、G=-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, while(t-) scanf(%d %s, scanf(%d %s, memset(max,0,sizeof(max); max00=0; for(i=1;i(maxi-1j+mapq1i-)? (maxi-1j-1+mapq1iq2j):(maxi-1j+mapq1i-); maxij=maxij(maxij-1+ma

8、p-q2j)?maxij:(maxij-1+map-q2j); printf(%dn,maxlen1len2); return 0; Hdu 2084 有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？ 输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 int a105105; int dp105105; int main() int i,j,n,t; scanf(%d, while(t-) scanf(%d, for(i=1;i=1;i-) for(j=1;jdpi+1j+1?dpi+1j:dpi+1j+1

9、); printf(%dn,dp11); return 0; SGU104 Little Shop of Flowers (DP) 分类：SGU DP 2012-04-08 22:54 107人阅读评论(0) 收藏举报 动态规划题 用dpij表示把前i束花放在前j个花瓶里所得到的最大的美观值(i #include #include #include #include using namespace std; const int maxn = 110; int f, v; int amaxnmaxn, dpmaxnmaxn; int premaxnmaxn; int DP() dp00 = 0;

10、 for (int i = 1; i 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, i int

11、 a100010; int main() int n,i,start,end,sum,max,sta,ti,k; scanf(%d, for(k=1;kmax)/这个if要放在下面的if语句的上面 max=sum; end=i;start=sta; if(sum micei.speed + 1, 最后找出最大的fi即可。注意此题还需要输出找到的序列中的老鼠的最原始的标号，因此不仅要在刚开始的时候把每个老鼠的最初的序号记下来，还要在进行状态转移的时候把当前的老鼠的位置标记下来。 #include struct haha int wei; int spe; int num; a1010; int

12、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 %

13、d, qsort(a+1,cnt-1,sizeof(struct haha),cmp); for(i=1;iaj.wei prei=j;/这里面记录的是倒序后面要倒着输出 end=1; max_l=l1; for(i=2;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) : 30 Accepted Submission(s) : 16 Probl

14、em Description Given 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 lar

15、gest sum is referred to as the maximal sub-rectangle. As an example, the maximal sub-rectangle of the array: 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 is in the lower left corner: 9 2 -4 1 -1 8 and has a sum of 15. Input The input consists of an N x N array of integers. The input begins with a single p

16、ositive 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,

17、 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. Output Output the sum of the maximal sub-rectangle. Sample Input 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 Sample Output 15 /* 题目大意：给定一个含有正数和负数的矩阵，求其子矩阵的和的最大值 一维的

18、情况很简单，如何把一维的情况转化为二维情况呢？ 例如，对于本题的测试数据： 我们可以每次任选几行，压缩成一行，这样就转化为了一维情况。 例如，我们求12行中的最大子矩阵：即矩阵高为2（12行），宽为1：4的矩阵，可以先把12行相加，得到9 0 -13 2，再求这个单行的最大子段，由此就可以求得12行的最大子矩阵。 */ #include #include int max,n; int map105105,b105; int dp() int i,sum=0,m=-1000; for(i=0;im) m=sum; return m; int main() int i,j,k,t,ans; whi

19、le(scanf(%d,ians?max:ans; printf(%dn,max); return 0; Advanced Fruits Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 877 Accepted Submission(s): 407 Special Judge Problem Description The company 21st Century Fruits has specialized in creating new

20、 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 creatio

21、ns 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 app

22、le 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. Y our job is to write a program that computes such a shortest name for a combinati

23、on of two given fruits. Y our algorithm should be efficient, otherwise it is unlikely that it will execute in the alloted time for long fruit names. Input Each 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 10

24、0 and only consist of alphabetic characters. Input is terminated by end of file. Output For 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 Input apple peach ananas banana pear peach Sample Output

25、appleach bananas pearch hdu ：http:/./doc/8ca4397da417866fb84a8e94.html /showproblem.php?pid=1503 题意： 两种水果杂交出一种新水果，现在给新水果取名，要求这个名字中包含了以前两种水果名字的字母，并且这个名字要尽量短。也就是说以前的一种水果名字arr1是新水果名字arr的子序列，另一种水果名字arr2也是新水果名字arr的子序列。要你求arr。 做法： 用求最长公共子序列的方法，求出arr1和arr2的最长公共子序列，然后再用递归思想，逐一输出，得到的就是最后答案。 #include #include

26、 #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;idpij-1) i-; else j-; /*取出最长公共子序列的字母*/ in

27、t 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 Rec

28、tangle in a Histogram Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5411 Accepted Submission(s): 1545 Problem Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in u