搜索
动态规划总结1.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.Sampleinput10512367911224450Sampleoutput9题目大意：用数轴描述一条高速公路，有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]代码：#includecstdio#includecstringusingnamespacestd;#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;iV;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;ki;++k)dp[i][j]=min(dp[i][j],dp[k][j-1]+sum[k+1][i]);}}printf(%d\n,dp[V][P]);}return0;}2.POJ1837DescriptionGigelhasastrangebalanceandhewantstopoiseit.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.SampleInput24-233458SampleOutput2题目大意：有一个天平，天平左右两边各有若干个钩子，总共有C个钩子，有G个钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。其中可以把天枰看做一个以x轴0点作为平衡点的横轴输入：24//C钩子数与G钩码数-23//负数：左边的钩子距离天平中央的距离；正数：右边的钩子距离天平中央的距离c[k]3458//G个重物的质量w[i]dp思路：每向天平中方一个重物，天平的状态就会改变，而这个状态可以由若干前一状态获得。首先定义一个平衡度j的概念当平衡度j=0时，说明天枰达到平衡，j0，说明天枰倾向右边（x轴右半轴），j0则相反那么此时可以把平衡度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]