动态规划题目

动态规划总结POJ1160PostOfficeTimeLimit:1000MSMemoryLimit:10000KTotalSubmissions:17936Accepted:9655DescriptionThereisastraighthighwaywithvillagesalongsidethehighway.Thehighwayisrepresentedasanintegeraxis,andthepositionofeachvillageisidentifiedwithasingleintegercoordinate.Therearenotwovillagesinthesameposition.Thedistancebetweentwopositionsistheabsolutevalueofthedifferenceoftheirintegercoordinates.Postofficeswillbebuiltinsome,butnotnecessarilyallofthevillages.Avillageandthepostofficeinithavethesameposition.Forbuildingthepostoffices,theirpositionsshouldbechosensothatthetotalsumofalldistancesbetweeneachvillageanditsnearestpostofficeisminimum.Youaretowriteaprogramwhich,giventhepositionsofthevillagesandthenumberofpostoffices,computestheleastpossiblesumofalldistancesbetweeneachvillageanditsnearestpostoffice.IntputYourprogramistoreadfromstandardinput.Thefirstlinecontainstwointegers:thefirstisthenumberofvillagesV,1<=V<=300,andthesecondisthenumberofpostofficesP,1<=P<=30,P<=V.ThesecondlinecontainsVintegersinincreasingorder.TheseVintegersarethepositionsofthevillages.ForeachpositionXitholdsthat1<=X<=10000.outputThefirstlinecontainsoneintegerS,whichisthesumofalldistancesbetweeneachvillageanditsnearestpostoffice.Sampleinput10512367911224450Sampleoutput题目大意：用数轴描述一条高速公路，有V个村庄，每一个村庄坐落在数轴的某个点上，需要选择P个村庄在其中建立邮局，要求每个村庄到最近邮局的距离和最小。题目分析：1、考虑在V个村庄中只建立【一个】邮局的情况，显然可以知道，将邮局建立在中间的那个村庄即可。也就是在a到b间建立一个邮局，若使消耗最小，则应该将邮局建立在（a+b）/2这个村庄上（可以通过画图知道）。2、下面考虑建立【多个】邮局的问题，可以这样将该问题拆分为若干子问题，在前i个村庄中建立j个邮局的最短距离，是在前【k】个村庄中建立【j-1】个邮局的最短距离与在【k+1】到第i个邮局建立【一个】邮局的最短距离的和。而建立一个邮局我们在上面已经求出。3、状态表示，由上面的讨论，可以开两个数组dp[i][j]:在前i个村庄中建立j个邮局的最小耗费sum[i][j]:在第i个村庄到第j个村庄中建立1个邮局的最小耗费那么就有转移方程：dp[i][j]=min(dp[i][j],dp[k][j-1]+sum[k+1][i])DP的边界状态即为dp[i][1]=sum[1][i];所要求的结果即为dp[vil_num][post_num];4、然后就说说求sum数组的优化问题，可以假定有6个村庄，村庄的坐标已知分别为p1,p2,p3,p4,p5,p6;那么，如果要求sum[1][4]的话邮局需要建立在2或者3处，放在2处的消耗为p4-p2+p3-p2+p2-p1=p4-p2+p3-p1放在3处的结果为p4-p3+p3-p2+p3-p1=p4+p3-p2-p1，可见，将邮局建在2处或3处是一样的。现在接着求sum[1][5],现在处于中点的村庄是3,那么1-4到3的距离和刚才已经求出了，即为sum[1][4],所以只需再加上5到3的距离即可。同样，求sum[1][6]的时候也可以用sum[1][5]加上6到中点的距离。所以有递推关系：sum[i][j]=sum[i][j-1]+p[j]-p[(i+j)/2]代码：#include<cstdio>#include<cstring>usingnamespacestd;#definemin(a,b)(a)<(b)?(a):(b)intdp[310][31];intsum[310][310];intV,P;intpos[310];intmain()(while(scanf(〃％d%d〃，&V,&P)!=EOF)(for(inti=1;i<=V;++i)scanf(〃%d〃,&pos[i]);memset(sum,0,sizeof(sum));for(inti=1;i<V;i++)(for(intj=i+1;j<=V;j++)(sum[i][j]=sum[i][j-1]+pos[j]-pos[(i+j)/2];}}for(inti=1;i<=V;++i)(dp[i][i]=0;dp[i][1]=sum[1][i];}for(intj=2;j<=P;++j)(//主意为什么把它放在外层for(inti=j+1;i<=V;++i)(dp[i][j]=9999999;for(intk=j-1;k<i;++k)dp[i][j]=min(dp[i][j],dp[k][j-1]+sum[k+1][i]);}}printf(〃%d\n〃,dp[V][P]);}return0;}2.POJ1837DescriptionGigelhasastrange"balance"andhewantstopoiseit.Actually,thedeviceisdifferentfromanyotherordinarybalance.Itorderstwoarmsofnegligibleweightandeacharm'slengthis15.SomehooksareattachedtothesearmsandGigelwantstohangupsomeweightsfromhiscollectionofGweights(1<=G<=20)knowingthattheseweightshavedistinctvaluesintherange1..25.Gigelmaydroopanyweightofanyhookbutheisforcedtousealltheweights.Finally,GigelmanagedtobalancethedeviceusingtheexperiencehegainedattheNationalOlympiadinInformatics.Nowhewouldliketoknowinhowmanywaysthedevicecanbebalanced.Knowingtherepartitionofthehooksandthesetoftheweightswriteaprogramthatcalculatesthenumberofpossibilitiestobalancethedevice.Itisguaranteedthatwillexistatleastonesolutionforeachtestcaseattheevaluation.InputTheinputhasthefollowingstructure:thefirstlinecontainsthenumberC(2<=C<=20)andthenumberG(2<=G<=20);thenextlinecontainsCintegernumbers(thesenumbersarealsodistinctandsortedinascendingorder)intherange-15..15representingtherepartitionofthehooks;eachnumberrepresentsthepositionrelativetothecenterofthebalanceontheXaxis(whennoweightsareattachedthedeviceisbalancedandlineduptotheXaxis;theabsolutevalueofthedistancesrepresentsthedistancebetweenthehookandthebalancecenterandthesignofthenumbersdeterminesthearmofthebalancetowhichthehookisattached:-fortheleftarmand'+'fortherightarm);•onthenextlinethereareGnatural,distinctandsortedinascendingordernumbersintherange1..25representingtheweights'values.OutputTheoutputcontainsthenumberMrepresentingthenumberofpossibilitiestopoisethebalance.SampleInput4-23458SampleOutput2题目大意:有一个天平，天平左右两边各有若干个钩子，总共有C个钩子，有G个钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。其中可以把天枰看做一个以x轴0点作为平衡点的横轴输入：4//C钩子数与G钩码数-23//负数：左边的钩子距离天平中央的距离；正数：右边的钩子距离天平中央的距离c[k]458//G个重物的质量w[i]dp思路：每向天平中方一个重物，天平的状态就会改变，而这个状态可以由若干前一状态获得。首先定义一个平衡度j的概念当平衡度j=0时，说明天枰达到平衡，j>0，说明天枰倾向右边（x轴右半轴），j<0则相反那么此时可以把平衡度j看做为衡量当前天枰状态的一个值因此可以定义一个状态数组dp[i][j]，意为在挂满前i个钩码时，平衡度为j的挂法的数量。由于距离c[i]的范围是-15~15，钩码重量的范围是1~25，钩码数量最大是20因此最极端的平衡度是所有物体都挂在最远端，因此平衡度最大值为j=15*20*25=7500。原则上就应该有dp[1~20][-7500~7500]。因此为了不让下标出现负数，做一个处理，使使得数组开为dp[1~20][0~15000]，则当j=7500时天枰为平衡状态那么每次挂上一个钩码后，对平衡状态的影响因素就是每个钩码的力臂力臂二重量*臂长二w[i]*c[k]那么若在挂上第i个砝码之前，天枰的平衡度为j（换言之把前i-1个钩码全部挂上天枰后，天枰的平衡度为j）则挂上第i个钩码后，即把前i个钩码全部挂上天枰后，天枰的平衡度j=j+w[i]*c[k]其中c[k]为天枰上钩子的位置，代表第i个钩码挂在不同位置会产生不同的平衡度不难想到，假设dp[i-1][j]的值已知，设dp[i-1][j]=num（即已知把前i-1个钩码全部挂上天枰后得到状态j的方法有num次）那么dp[i][j+w[i]*c[k]]=dp[i-1][j]=num(即以此为前提，在第k个钩子挂上第i个钩码后，得到状态j+w[i]*c[k]的方法也为num次)想到这里，利用递归思想，不难得出状态方程dp[i][j+w[i]*c[k]]=S(dp[i-1][j])有些前辈推导方式稍微有点不同，得到的状态方程为dp[i][j]=S(dp[i-1][j-c[i]*w[i]])其实两条方程是等价的，这个可以简单验证出来，而且若首先推导到第二条方程，也必须转化为第一条方程，这是为了避免下标出现负数结论：最终转化为01背包问题状态方程dp[i][j+w[i]*c[k]]=S(dp[i-1][j])初始化：dp[0][7500]=1;//不挂任何重物时天枰平衡，此为一个方法复杂度O(C*G*15000)完全可以接受/*MemoryTime1496K0MS我所使用的解题方法，由于dp状态方程组申请空间比较大大若dp为局部数组，则会部分机器执行程序时可能由于内存不足会无法响应所以推荐定义dp为全局数组，优先分配内存*/#include<iostream>usingnamespacestd;intdp[21][15001];//状态数组dp[i][j]//放入（挂上）前i个物品（钩码）后，达到j状态的方法数intmain（inti,intj,intk）{intn;//挂钩数intg;//钩码数intc[21];〃挂钩位置intw[21];//钩码重量/*Input*/cin>>n>>g;for(i=1;i<=n;i++)cin>>c[i];for(i=1;i<=g;i++)cin>>w[i];/*Initial*/memset(dp,0,sizeof(dp));//达到每个状态的方法数初始化为0dp[0][7500]=1;//7500为天枰达到平衡状态时的平衡度//放入前0个物品后，天枰达到平衡状态7500的方法有1个，就是不挂钩码/*DP*/for(i=1;i<=g;i++)for(j=0;j<=15000;j++)if(dp[i-1][j])//优化，当放入i-1个物品时状态j已经出现且被统计过方法数，则直接使用统计结果//否则忽略当前状态jfor(k=1;k<=n;k++)dp[i][j+w[i]*c[k]]+=dp[i-1][j];//状态方程/*Output*/cout<<dp[g][7500]<<endl;return0;}3.选择客栈【问题描述】丽江河边有n家很有特色的客栈，客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰(总共k种，用整数0~k-1表示)，且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间(包括他们住的客栈），且咖啡店的最低消费不超过p。他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。【输入】输入文件hotel.in，共n+1行。第一行三个整数n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；接下来的n行，第i+1行两个整数，之间用一个空格隔开，分别表示i号客栈的装饰色调和i号客栈的咖啡店的最低消费。【输出】输出文件名为hotel.out。输出只有一行，一个整数，表示可选的住宿方案的总数。【输入输出样例1】hotel.inhotel.out52305133021415【输入输出样例说明】客栈编号①②③④⑤色调01011最低消费532452人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤，但是若选择住4、5号客栈的话，4、5号客栈之间的咖啡店的最低消费是4,而两人能承受的最低消费是3元，所以不满足要求。因此只有前3种方案可选。【数据范围】对于30%的数据，有nW100；对于50%的数据，有nW1,000；对于100%的数据，有2WnW200,000，0<kW50，0WpW100，0W最低消费W100。【一句话题意】合法区间［l,r］定义：l,r的色调相同，且［l,r］之间存在一个最低消费不超过P。求合法区间总数。【考察知识点】二分查找/枚举：O"：看完题目后不知所云，再多看几遍，一个O(n"3)的算法有了一点雏形。用两层循环枚举区间的左右端点1、r，再用一层循环判断区间内是否有可行的咖啡店，累计即可。这个算法思维难度和编程难度都非常低，但是只能过30%的数据，可以作为对拍程序备份。：O(nk)再仔细思考，发现题中合法区间的限制条件其实很强。首先区间端点的色调必须相同，其次区间内必须要存在一个咖啡店最低消费不超过P。因此，如果我们用一层循环枚举左端点，并很快找到右端点的可行数，那么题目就能解决了。这里置答案为变量ans，千万注意类型要为int64这里首先要用到区间部分和优化。设sum[i,j]为前i个客栈中，色调为j的客栈总数，那么：sum[i,j]=sum[i-1,j](color[i]<>j)sum[i,j]=sum[i-1,j]+1(color[i]=j)这里要用O(NK)的复杂度，是算法的瓶颈所在，不过对于题中的数据范围已经足够了。并且具体实现可以先用数组赋值sum[i]=sum[i-1]，然后再为sum[i,color[i]]+1，应该会快很多。我们还需要解决的问题就是，已知了L，如何快速找到R的可行范围？再次注意区间内必须要存在一个咖啡店最低消费不超过P。因此，如果L就是一个最低消费不超过P的咖啡店，那么R可以取到[L+1,n]中所有色调为color[L]的客栈，即ans=ans+sum[n,color[L]]-sum[L,color[L]]；如果L是一个最低消费超过P的咖啡店，那么我们要找到一个TE[L+1,n]，且咖啡店T的最低消费不超过P，那么R就可以取到[T,n]中所有色调为color[L]的客栈，即ans=ans+sum[n,color[L]]-sum[TT,color[L]]。问题是我们如何找到这个T,其实很简单，二分查找即可。再次预设一个数组，保存所有最低消费不超过P的咖啡店序号，二分查找L即可。注意这里L一定不存在这个数组中，因此找到的应该是最靠近L且大于L的序号，细节处理很重要。找不到返回-1，不用累加ans就是了。：O(nlogn)这个办法比②更优一些。来自Clarkok的做法。用list[i,j]表示颜色为i的第j个客栈，也就是将客栈按照颜色紧缩存储。另用pos[i]表示第i个旅馆在list[color[i]]中的位置。用线段树/ST算法(推荐)预处理出区间消费的最小值，也就是min{cost[i..j]}，易得到min[k,i]是非增的，注意这是后面二分的关键。然后枚举第二个人，在list[color[i]]中用二分找到一个j满足min[j，i]〈二P，那么ans=ans+j，因为list[color[i],1..j]中必然都是颜色为color[i]，且区间最小值也都〈二P。：O(n)这应该是最优算法了，无论从空间、时间、编程复杂度方面来说。这个算法转自上善若水记f⑴为第1~i的客栈中，编号最大的最低消费小于p的旅馆编号；r(i)为1~i-1号旅馆中，编号最大的与第i号旅馆色调相同的旅馆编号，countl(i)为第1~i-1号旅馆中与第i号旅馆色调相同旅馆数目，count2(i)为第1~i-1号旅馆中与第i号旅馆色调相同，且到第i号旅馆的路上存在最低消费不大于p的旅馆的旅馆数目。⑴若f(i)<r(i)，那么必然有f(i)=f(r(i))，故count2(i)=count2(r(i))。(II)若f(i)>=r(i)，那么第1~r(i)号旅馆中，所有与第i号旅馆色调相同的旅馆到第i号旅馆的路上必然存在一个旅馆的最低消费不大于p。故此时count2(i)=count1(i)。从1到n扫描一次即可，时间复杂度O(n)。具体实现时可以将数组压缩，空间复杂度O(k)。【时间复杂度】最低O(n)代码：#include<stdio.h>#include<stdlib.h>intn,k,p;intcolor[200000],price[200000];intflag[50]={0};intsum[50]={0};intnum[50]={0};intrealnum[50]={0};voidchangeflag(){inti;for(i=0;i<k;i++){flag[i]=1;}}intgetsum(){inti;intx=0;for(i=0;i<k;i++){x+=sum[i];}returnx;}voidrefresh(){inti;for(i=0;i<k;i++)realnum[i]=num[i];}}intmain(){inti;scanf(〃％d%d%d〃，&n,&k,&p);for(i=0;i<n;i++){scanf(〃％d%d〃,&color[i],&price[i]);num[color[i]]++;if(price[i]<=p){changeflag();refresh();}if(num[color[i]]!=1)//该酒店不是第一次出现{if(flag[color[i]]==1){//refresh();sum[color[i]]+=(num[color[i]]-1);}else{sum[color[i]]+=realnum[color[i]];}if(price[i]>p)flag[color[i]]=0;}}printf(〃％d\n〃,getsum());return0;}4.POJ1080(此题已经有了，不出此题的测试数据)//题目过长详见：/problem?id=1080LCS的变形而已注意LCS的子串可以是离散的，不必连续，用动态规划设dp[i][j]为取s1第i个字符，s2第j个字符时的最大分值则决定dp为最优的情况有三种(score□□为s1[i]和s2[j]两符号的分数)：1、si取第i个字母，s2取"-”：dp[i-1][j]+score[s1[i-1]]['-'];2、s1取"-”，s2取第j个字母：dp[i][jT]+score['-'][s2[j-1]];3、s1取第i个字母，s2取第j个字母：dp[i-1][j-1]+score[s1[i-1]][s2[j-1]];即dp[i][j]=max(dp[iT][j]+score[s1[i-1]]['-'],dp[i][j-1]+score['-'][s2[j-1]],dp[i-1][j-1]+score[s1[i-1]][s2[j-1]]);注意初始化不仅仅只有dp[0][0]=0也不仅仅是dp[0][0]=0dp[1][0]=score[s1[i-1]]['-']dp[0][1]=score：'-']：s2[j-1]]必须全面考虑到所有情况，当i=j=0时，dp：i]：j]=0当i=0时，dp：0,j]=dp：0]：j-1]+score：'-']：s2：j-1]]当j=0时，dp：i,0]=dp：i-1]：0]+score：s1：i-1]]：'-']//MemoryTime//300K0MS#include<iostream>usingnamespacestd;constintinf=-5;//无穷小intscore：'T'+1]：'T'+1];//积分表voidinitial(void)//打表score：'A']：'A']=5;score['C']['C']=5;score['G']['G']=5;score['T']['T']=5;score['-']['-']=inf;score['A']['C']=score['C']['A']=-1;score['A']['G']=score['G']['A']=-2;score['A']['T']=score['T']['A']=-1;score['A']['-']=score['-']['A']=-3;score['C']['G']=score['G']['C']=-3;score['C']['T']=score['T']['C']=-2;score['C']['-']=score['-']['C']=-4;score['G']['T']=score['T']['G']=-2;score['G']['-']=score['-']['G']=-2;score['T']['-']=score['-']['T']=-1;return;intmax(inta,intb,intc){intk=(b>c?b:c);returna>k?a:k;//注意求三个数最大值时，a>b?a:(b>c?b:c)在C++中是错误的}//b的值没有因为(b>c?b:c)而改变，必须把三个数拆开求最大值intmain(inti,intj){initial();inttest;cin>>test;while(test--){intlen1,len2;cin>>len1;char*s1=newchar[len1+1];cin>>s1;cin>>len2;char*s2=newchar[len2+1];cin>>s2;int**dp=newint*[len1+1];//申请动态二维数组，第一维dp[0]=newint[len2+1];dp[0][0]=0;for(i=1;i<=len1;i++){dp[i]=newint[len2+1];//申请动态二维数组，第二维dp[i][0]=dp[i-1][0]+score[s1[i-1]]['-'];〃注意下标，dp数组是从1开始，s和s2都是从0开始}for(j=1;j<=len2;j++)dp[0][j]=dp[0][j-1]+score['-'][s2[j-1]]