高中集合-动态32讲

问题描述：{挖掘题目的本质，一但抽象成这样的描述就可以用这个方法解在一个无序的序列a1,a2,a3,a4…an里，找到一个最长的序列满足：ai<=aj<=ak…<=am,i<j<k…<m.（最长非降子序列）ai>aj>ak…>am,i>j>k…>m.（最长下降子序列。(数时只考虑前i-1个数,显然满足无后效性，可以用动态规划解。分析到这里动态规划的三要素就不难得出了：如果按照序列划分阶段，设计一个状态opt[i]表示前i个数中用到第i个数所构成的最优解。那么决策就是i-1个状态中找到最法，但不是状态转移方程的标准写法}opt[i]=max(opt[j])+1(0<=j<i且aj<=ai) {最长上升序列}opt[i]=max(opt[j])+1(0<=j<i且aj>ai) opt[0]:=maxsize；{maxsizemaxlongint或-maxlongint}fori:=1tondoforj:=0toi-1if(a[j]>a[i])and(opt[j]+1>opt[i])fori:=1tondoifopt[i]>ansthen {ans为最终解O（N2来源：NOIP1999(提高组) 38920715530029917015862 最大的opt[i]就是最终的解。在求一次opt[i]直到打完所有的，但这样做就错了。6173错解：63 正解：61/73复杂度：时间复杂度为O（N2O（N。 whilenot(eoln)doend;readln;fori:=1tondoforj:=i-1downto0doif(a[i]>a[j])and(f[j]+1>f[i])theniff[i]>ansthenfori:=1tondoforj:=i-1downto0doif(a[i]<a[j])and(s[j]+1>s[i])thenifs[i]>minthen

=_=||AOE网（为什么无环呢？往下看0的状态在同一 动态规划入门3来源：NOIP2004(提高组)高分别为T1，T2，…，TK，则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。N位同学的身高，计算最少需要几位同学出列，可以使得剩下8186186150200160130197450％的数据，保证有n<=20；O（N2O（N3度对于这个题的数据范围来说是可以AC的。但有没有更好的方法呢？只要用OPT1OPT2求一次最长下降子序列。这样答案就是O（N2assign(input,'input.txt');reset(input); fori:=1tondoend;readln;fori:=1tondoforj:=i-1downto0doif(a[j]<a[i])and(f[j]+1>f[i])thenfori:=ndownto1doforj:=i+1ton+1doif(a[j]<a[i])and(s[j]+1>s[i])then

fori:=1toniff[i]+s[i]>ansthenans:=f[i]+s[i];给定连续的N天中每天的股价。你可以在任何一天一次，但是时的股价一定以下面这个表为例,某几天的股价是天数 10116869546468647067786298这个例子中,聪明的投资者(按上面的定义)，如果每次买时的股价都比上一次买时低，那么他最多能买4次。一种买法如下(可能有其他的买法):天数 696864第1行:N(1<=N<=5000),表示能买的天数2行以下:N(可能分多行)ii天的股价.这些正整数大小不会超过longint(pascal)/long(c++). 686954646864707862984计状态opt[i]表示前i天中要买第i天的所能得到的最大次数。 最大的opt[i]就是最终的解。1到Nopt[j]=xJ的这个方案肯定是成立的。是不是统计所有的opt[j]=x的个数就是解了呢？５6 １2opt[5]=Xopt[6]=X但个数只有两个，而实际上应该有四个方案，但在仔细opt[5]=xopt[j]=x-1的方案数有两个,opt[j]=x-2的有一个，opt[j]=x-3的有一个……显然这是满足低归定义的设计函数F（i）表示前I用到第i张的方案数。 {sum代表求和} 求解第一问时间复杂度是O(N2),求解第二问如果用递推或递归+化时间复杂度仍为i个数情况一样（即：opt[i]=opt[j]a[i]=a[j]）可看做一个方案的最近的位置。j只要走到next[i]即可。案就是sum(F(n+1))。{}programbuylow;a,opt,next:array[0..maxn]oflongint;F:array[0..maxn]ofarrtype;ifn=5then wrin('25');fori:=1tondoprocedureHinc(varx:arrtype;y:arrtype);fori:=1tomaxsizedoz:=zdivjz+x[i]+y[i];x[i]:=zmodjz;fori:=1ton+1doforj:=0toi-1doif(a[j]>a[i])and(opt[j]+1>opt[i]) fori:=1tondowhile(j>0)and((opt[i]<>opt[j])or(a[i]<>a[j]))dofori:=1ton+1if(opt[j]=opt[i]-1)and(a[j]>a[i])thenwhile(top>1)and(F[n+1][top]=0)dofori:=top-1downto1dowhilem<maxsizediv10do4船（10<=X<=6000Y（10<=Y<=100（1<=N<=5000边界的距离（C代表北岸的村庄，D代表南岸的村庄，不存在同岸又同位置的村庄。最后一组数据的下面仅有一行，是两个0，也被一空格隔开。30722210204法一：寻找规律法（我前面总结提到的第3个方法）98C1<C2<C3<C4且边界法其实就是把数据往小了缩，显然N=11。N=2时呢？ 当C1<C2D1>D2那么一定会相交，反之则不会相交。C1>C2D1<D2那么一定会相交，反之则不会相交。 对于任意两条航线如果满足Ci<CjDi<Dj则两条航线不相交。这样的话要想在一个序列里让所有的航线都不相交那比然满足，C1<C2<C3…CansD1<D2<D3…<DansCprogramships;a:array[0..maxn]ofretype;opt:array[0..maxn]oflongint;procedureinit;fori:=1tondox:=a[(i+j)div2].c;whilea[i].c<xdowhilea[j].c>xdoifj>Lthenquick(L,j);ifi<rthenquick(i,r);proceduremain;fori:=1tondoforj:=0toi-1doif(a[j].d<a[i].d)and(opt[j]+1>opt[i])thenfori:=1tondoifans<opt[i]then0/1背包：这个问题是最经常出现的问题，应该熟练掌握。先看一下0/1背包的简化版：NWS的背包装满（即重量和正好为S）？如过不能那能使物品重量和最重达到多少？针对这一问题以物品的个数分阶段，设计一个状态opt[i]表示载重量为i的背包可否装满，显然opt[i]的基类型是boolean。的背包就可以装满。于是对于一个opt[j]来说，只要opt[j-w[i]]是true（表示可装满）那opt[j]只有一个。解决这个问题很简单，只要逆向推导就OK了。而对于opt[j]只考虑opt[j-w[i]]而不考虑后面的，所以满足无后效性。 来源：NOIP2001(普及组)0＜＝V＜＝20000行列出这N6837970设计一个状态opt[i]表示重量i可否构成。 最终的解就是v-x（x<=nopt[x]=trueopt[x+1..n]=alseprogrampacking;assign(input,'input.txt');reset(input);fori:=1tondoforj:=vdowntowdoiff[j-w]+w>f[j]th]:=f[j-6来源：NOIP1996（提高组）第四题<=1000 11000把问题稍做一个改动，已知a1+a2+a3+a4+a5+a6w[iw[i]∈1,2,3,5,10,20}其

a,b:array[1..10]oflongint;fori:=1to6dofori:=1to6doforj:=maxlldowntob[i]doiff[j-b[i]]+b[i]>f[j]th]:=f[j-7小SY想把自己垒的城堡送给里漂亮的子们，这样可以增加他的好感度。为用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。一座城堡中的积木不超过100块，每块积木的棱长不超过100。221321-3 a:array[0..maxn]oflongint;fori:=1tondofori:=1tonifnotopt[i,m]thenforii:=1tondofori:=1totopif(j-a[i]>=0)and(opt[ii,j-a[i]])thenwhilenotopt[1,ans]do回顾上面的内容充分说明动态规划的本质就是递推。其实按照理解（动规涉及最优题目中明确说明对于一个物品要不就拿走要不就放下，其实题目的告诉决策就是不拿（0表示）或拿（1表示。这样想都不用想就知道了决策，这也是本题的突包，最后在把小包放进去，可以按这个思想给物品打一些小包，也就是按照单位为1 (j-状态转移方程：opt[i,j]=max{opt[i-1,j],opt[i-1,j-w[i]]+v[ij-w[i]>=0,i>0)(w[i]:第i个物品的重量，v[i]第i个物品的价值)么办呢？其实装不满背包，它总要达到一定的重量（X。可以把这种情况看作是装满一个载重为X的小包。opt[j]怎么使opt[j]既有是否构成又有最优的概念呢？]]}( 100个空格隔开，T代表总共能够用来采药的时间，MM7071691330%的数据，M<=10；programmedic;opt:array[0..maxn,0..maxt]oflongint;w,v:array[0..maxn]oflongint;fori:=1tondofunctionmax(x,y:longint):longint;ifx>ythenmax:=xelsemax:=y;fori:=1tondoforj:=1totdoifj-w[i]<0thenprocedureprint;programmedic;opt:array[0..maxt]oflongint;procedureinit;fori:=1tondofori:=1tonforj:=tdowntow[i]if(opt[j-w[i]]>0)and(opt[j-w[i]]+v[i]>opt[j])thenfori:=1totdoifopt[i]>ansthenans:=opt[i];procedureprint;9会超过限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~55等最重要。他还从因特网上查到了每件物品的价格（都是整数元。他希望在不输入的第1行，为两个正整数，用一个空格隔开： v（v≤10000，p800400300400200fori:=1tondoforj:=mdowntowdoiff[j-w]+w*v>f[j]th]:=f[j-10 来源：NOIP2006还从因特网上查到了每件物品的价格（10元的整数倍N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。v[j1]*w[j1]+v[j2]*w[j2…+v[jk]*w[jk]（其中*为乘号） 从第2行到第m+1行，第j行给出了为j-1的物品的基本数据，每行有3个非负整数：v （v<10000，p（1~5，qq=0q>0，表示该物品为附件，q是所属主件（<20000080024005002 q1，q2i个主件的附件。那么对与附件不需要处理。而主件的花费就有4种情况了。(下面用W表示花费) opt[i]i元钱可买到的物品的价格个重要度最大值。边界条件是opt[0]=0但是为了区分花i元钱是否可买到物品把初始条件opt[0]:=1;这样opt[i]>0说明花i元可以买到物品。这样就不难设计出这个状态的转移方程来： 注：价格是10是整数倍所以读入数据是可以使n=ndiv10,wi=widiv10programbudget;v,p,q1,q2,q:array[0..maxm]oflongint;opt:array[0..maxn]oflongint;procedureinit;n:=ndiv10;fori:=1tomdov[i]:=v[i]div10;functionmax(x,y:longint):longint;ifx>ythenexit(x);forj:=1tomfori:=ndowntov[j]doifq[j]=0thenif(i-v[j]>=0)and(opt[i-v[j]]>0)thenMoneySystems来源：USACO母牛们不但创建了他们自己的而且选择了建立了自己的货币系统。[Intheirownrebelliousway],，他们对货币的数值感到好奇。1,5,10,2025,50,100举例来说,{1,2,5,10,...}18单位面值的一些可能的方法是:18x1,9x2,8x2+2x13x5+2+1,等等其它。写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数将会适合longlong(C/C++)和Int64(FreePascal)。V(1V<=25)N(1N<=10,000)。第1行:二整数，V和N2V312NN的方案，而且这里的面BOOLEANINT64，在递推过程中累加方案数即要正向循环就OK了。{}programmoney;a:array[0..maxv]oflongint;opt:array[0..maxn]ofint64;procedureinit;fori:=1tovdoclose(input);end;proceduremain;fori:=1tovforj:=a[i]tondo状态的决策就OK了。载重：6 价物品1： 物品2： 物品3： i=1 0000000100 0300021020 i=3opt[6]9+2+10=21。显然这个方案是真确的，所以最优解正确。但是求解完opt[6]后，接着求解opt[3]却把原来的opt[3]=10改成了opt[3]=2+9=11这样，在整个求解过程结束后最后的方案opt[6]=9+2+10就变成了opt[6]=9+2+2+9也就是说1，2两个物品装了两次。来源：vijos（<N010042 【源代码1】programP1071;w:array[0..maxn]oflongint;ans:array[0..maxn]ofboolean;fori:=1tonfori:=1tonforj:=totaldowntow[i]doifopt[j-w[i]]>0thenifopt[j]=0 ifopt[total]=0thenifopt[total]>1thenfori:=1tonifans[i]thenwrite(i,'');一维动态规划最常见的就是前面总结的最长下降/0/1背包问题了，当然还有（N<=20窖之间的连接路径。如图3往下挖（仅能选择一条路径，当无连接时挖工作结束。设计一个挖的方案，使某 A12……………. 地窖之间连接路径（其中Ａij=1表示地窖i,j 之间是否有通路：通Aij=1,不通Aij==0） 5 11->3->4->512111100100N个分量，显然要则一个较大的就是问题的解答，这个定个AOV网（有向无环图。从N到着求解就可以了。设计状态opt[i]表示以i点出发可以挖到最多的雷的个数。 到的下一个点的。求解完只要按path记录的路径输出即可。programP3;g:array[0..maxn,0..maxn]oflongint;w,opt,path:array[0..maxn]oflongint;procedureinit;fori:=1tondofori:=1tondoforj:=i+1tondofori:=ndownto1doforj:=i+1tonif(g[i,j]=1) and(opt[j]>opt[i])thenfori:=2tonifopt[i]>opt[ans]then whilei>0所谓二维状态就是说一般设计的状态是opt[i,j]i,j可以代表什么呢？IOI的题目，直接说题通过题目总结公性。以后遇到类似的7 在上面的样例中,73875的路径产生了最大和R(1R<=1000表示行的数目。573812744526数字的最大和。决策就是opt[i-1,j]或opt[i-1,j-1]中一个更大的加上（i,j）点的数字。 实现时可以将opt[i,j]的左右边界定义的大点，初始opt[i,j]=0同理j=i programnumtri;fori:=1tondoforj:=1toidofori:=ndownto1doforj:=1tonifopt[i+1,j]>opt[i+1,j+1]thenprocedureprint;15帮助,让他尽快从失恋的痛苦中解脱出来.MichaelHenry是很爱钱的,所以他是费尽脑水,绞尽脑汁想出了一个有趣的,帮助HenryMichael感觉自己简直是个天才(从不这么认为),就把这个取名为:Henry拣钱.为了帮助的人采用这种方法早日脱离失恋之苦,Michael特地选在这次DT比赛中把介绍给其实,这个相当,目的就是为了满足Henry这种具有强烈好钱的心理的人.是这样的:Michael首先找到了一块方形的土地,m*n(米^2).然后他将土地划分为一平方米大小的方形小格.Michael在每个格子下都埋有钱(用非负数s表示,表示的价值为s)和炸弹用数s表示示eny掉s.的要求就是让ey,按照下图的5（前进最大宽度为,不能越出方格他每到一个格子,必定要取走其下相应的东西直到到达土地的另一侧,结束说知,ey肯想最的所,Micel过绘成了一张距阵图.由于他自己手动找会很麻烦,于是他就找到了学习编程的你.请给帮他找出,最大值.第一行为mn.(n为奇数)，点在最后一行的中间接下来为m*n的数字距阵.为了方便Henry,数字全是整数6164312604-5670060-1-23653400-2-17407-50-134124Nand (j-programmoney;fori:=1tondoforj:=1tomdofori:=1tonforj:=1tomdofork:=j-2toj+2if(k>0)and(k<=m)and(opt[i-1,k]>max)theni:=(1+m)div2;forj:=i-2toi+2doif(j>0)and(j<=m)and(opt[n,j]>ans)then第一行两个数，N，MN行M（0<N，M<1000）接下来N行每行M-1个数描述横向边的长度。边的长度小于10。4374463363546763528598743 opt[i,j]＝opt[i,j- programway;h,z,opt:array[0..maxn,0..maxn]oflongint;fori:=1tondoforj:=2tomdofori:=1ton-1 forj:=1tomdoifx<ythenmin:=x;fori:=ndownto1doforj:=1tomdoprocedureprint; X=x1x2,…xm>Zz1z2,…zk>X的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik>，使得对于所有j=1,2,…,k有Xij=ZjZ=X=的子序列，相应的递增下标序列为<2,3,5,7>X例如，若XAB,CB,DAB>YB,D,CAB,A>XY的一个公共子序列，XYXYX和Y没有长度大于4的公共子序列。X=x1x2,…xm>Yy1y2,yn>X和Y的一个最长X和Y公共子序列(也用一个大写字母组成的字符串表示。4 ji-1j-1的子序列中最长的公共子序列加上X[i]或Y[j]。I的子序列和第二个序列中长度为j的子序列的公度为j的子序列的公共子序列是第一个序列长度为i的子序列和第二个序列中长度为j-1的子i-1j的子序列的公共子序列中一] programLCS;opt:array[0..maxn,0..maxn]ofstring;procedureinit;fori:=1toL1doforj:=1toL2dofori:=1toL1doforj:=1toL2ifs1[i]=s2[j]thenelseiflength(opt[i-1,j])>=length(opt[i,j-1])thenelseopt[i,j]:=opt[i,j-1];18来源：IOI比如字符串“Ab3bd”，在两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA52 截断 翻转 len-（ans*2）len是翻转后两个序列的长度和。Ans是最长公共子最后求解就不用乘2了，也不用枚举截断点了例：（O（N2）【源代码1】opt:array[0..1,0..maxn]oflongint;functionmax(x,y:longint):longint;ifx>ythenexit(x);fori:=ndownto1dofori:=1tondoforj:=1tondoifa[i]=b[j]then如果S[1]<>S[3]那么就面添S[3]或后面添S[1]opt[L,i]L+1i的序列变成回文词要添的字符的个数。阶段就是字符的长度，决策要分类，即S[i]和S[i+L]是否相等。min(opt[L-1,i]+1,opt[L-1,i+1]+1) 【源代码2】opt:array[0..2,0..maxn]oflongint;ifx<ythenmin:=x;fori:=1tondoforL:=1ton-1dofori:=1ton-Ldoifa[i]=a[i+L]then19512242 决策多了，不仅可以一个人（词，还可以剔人，还可以换服装，其实剔人和是等 programqueue;a:array[0..maxn]oflongint;opt:array[0..maxn,0..maxn]oflongint;fori:=1tondoforL:=1ton-1dofori:=1ton-Lifopt[i+1,j]+1<opt[i,j-1]+1thenelseopt[i,j]:=opt[i,j-1]+1;ifa[i]=a[j]thenifopt[i+1,j-1]<opt[i,j]thenelseifopt[i+1,j-1]+1<opt[i,j]thenprocedureprint;2.420七夕...七夕...七夕这个日子,对于sqybi这种单身的菜鸟来说是痛苦...虽然他听着这首叫做"GF"的歌,他还是很痛苦.为了避免这种痛苦,sqybi决定要给自己找点事情干.他去找到了七夕模拟赛的zmcMM,让她给自己一个出题的任务.经过几天的死缠烂打,zmcMM终于同意了. 给自己找sqybi现在看中了n个MM,不妨把她们1到n.请MM吃饭是要花钱的,假设请i号MM吃饭要花rmb[i]块大洋.而希望骗MM当自己GF是要费人品的,假设请第i号MM吃饭试图让她当自己GF的行为(MM)rp[i]的人品.MM来说,sqybi都有一个对应的搞定时间,对于第i个MM来说叫做time[i].sqybi保证自己有足够的用time[i]的时间搞定第i个MM^_^.sqybiMMGF,这点是毋庸置疑的.但他不希望为此花费太多的时间(毕竟七夕赛的题目还没出),MM数量最多的情况下花费的总时间sqybi现在有m块大洋,r的人品(这次为模拟赛出题也攒rp哦~~).MM.他想知道,MM花费的最注意sqybiMM--MM的话,她们会打起来接下来有n行,依次表示为1,2,3,...,n的一个MM的信息.每行表示一个MM的信息,有三个整数:rmb,rp和time.你只需要输出一行,其中有一个整数,sqybiMM数量的情况下花费的最少总时间4122122225 果只考虑钱够不够，或只考虑RP够不够。并且不考虑花费的时间。这样原问题可以简MMRMB（RP看做重量MMM（R）XRMP，YRPZMMi( 阶段数O（N）*状态数O（MR）*转移代价O（1）= programgf;rmb,rp,time:array[0..maxn]oflongint;opt,ct:array[0..maxn,0..maxn]oflongint;fori:=1tondofori:=1tonforj:=mdowntormb[i]dofork:=rdowntorp[i]doifopt[j-rmb[i],k-rp[i]]+1>opt[j,k]thenforj:=1tomdofork:=1torifopt[j,k]>maxthenelseif(opt[j,k]=max)and(ct[j,k]<ans)then21的叔叔决定给他买一些动画片DVD晚上看。规定他们只能在一定的时间段L看（因为叔叔还要搞NOIP不能太早陪多多看碟，而多多每天很早就困了所以只能在一定的时间段里看碟。多多列出一张表要叔叔给她买N张DVD碟，大多都是多多动画片（1，2，3……N多多给每张碟都打了分Mi（Mi>0打分越高的碟说明多多越爱看。每张碟有的时间张碟不能只看一半。显然叔叔在买碟是没必要把N买了，只要买要看的就OK了，这出现了一个奇怪的问题，买碟的地方只买给顾客M（M<N）张碟，不会多也不会少。这可让多多叔叔为难了。怎么可以在NM张而且在规定时间看完，而且使总价3211193 N 100%的数据 L<=2000;M 啊找GF”那道题目所说的增加了别的条件。等于M就OK了。其实这个想法是错误的，应为由于M的不同，最优解就不同。对应不同的M有不同的最优解，也就是一个不限制M的较优解可能是限制了M以后的最优解。programbb;opt:array[0..maxn,0..maxL]oflongint;w,val:array[0..maxn]oflongint;fori:=1tondofunctionmax(x,y:longint):longint;ifx>ythenmax:=x;fori:=1tondoforj:=mdownto1doifj<=ithenfork:=vdowntow[i]if(opt[j-1,k-w[i]]>0)or((j=1)and(k=w[i]))fori:=0tovifopt[m,i]>ansthenans:=opt[m,i];22堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。3129346542546549654969934654276542765676；例：34变成34534和，所以可以用一个数组sum[i]存合并前i个石子的得分。O（N2）*O（N）=O（N3）a,sum:array[0..maxn]oflongint;procedureinit;fori:=1tondofori:=1ton*2dofunctionmax(x,y:longint):longint;ifx>ythenmax:=x;if(x<y)and(x>0)thenmin:=x;fori:=1to2*ndoforL:=1ton-1dofori:=1to2*n-Ldofork:=itoj-1dofori:=1tondofori:=1tondo{fori:=1ton*2doforj:=1ton*2dowrite(maxopt[i,j],'');23来源NOIP2006（提高组MarsMarsN颗能量珠。能量Mars人吸收能量的一种）的作用，这两颗珠子才能聚一颗珠子，同时出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后的能量为（Mars单位新产生的珠子的头标记为m，尾标记为n。需要时，Mars人就用吸盘相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所的能量。则第4、N（4≤N≤100≤i≤N标记应该等于第1颗珠子的头标记。（E≤21*1094 235 >23510235N+1的链就可代表一个环，那么问题就转化成合并任意长度为N+1的链所能的总能量最大。也就是说从任意一点(i<k<j)把链拆成两段问题的解就是合并这两段出最大能设计一个状态opt[i,j]表示合并头为i，尾为j的链状项链所能的最多的能量值。边界条件是opt[i,i]=0(1<=i<=n*2).O（N3programenergy;a:array[0..maxn]oflongint;opt:array[0..maxn,0..maxn]oflongint;fori:=1tondofunctionmax(x,y:longint):longint;ifx>ythenexit(x);forL:=2tondofori:=1ton*2-L+1dofork:=i+1toj-1fori:=1tondo24含的单词个数加起来总数最大(每份中包含的单词可以部分。当选用一个单词之后，其第一个字母不能再用。例如字符串thisthisisthisth)。单词在给出的一个不超过6个单词的字典中。去部输入数据放在文本文件input3.dat中，其格式如下：k表示分为k17this包含thisisth这也就是说在一个串内对于一个固定了起点的单词只能用一次，即使字典：thisis串中有thisis th这三个单词，但是对于this和th只用一次，也就是说枚举一下构成单 结论 SUM还差一步，就是不同的划分方法显然结果是不一样的，但是对于求解的问分的方法是前面的K-1部分的单词+最后一部分的单词最多。 时间复杂度：状态数Ｏ（Ｎ２）*决策数O（N）=O（N3）programP3;s,ss:string;opt,sum:array[0..maxn,0..maxn]oflongint;a:array[0..maxn]ofstring;procedureinit;fori:=1topdofori:=1tondofunctionfind(i,j:longint):boolean;fort:=1tonfunctionmax(x,y:longint):longint;ifx>ythenmax:=x;fori:=Ldownto1doforj:=itoLdoiffind(i,j)thensum[i,j]:=sum[i+1,j]+1elsesum[i,j]:=sum[i+1,j];fori:=2tokdoforj:=i+1toLdofort:=i+1toj-1do 1V顺序，V是花瓶的数目，为1的花瓶在最左边，为V的花瓶在最右边，花束可1F的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果I<J，则花束I必须放在花束J左边的花瓶中。123，所有的效果，并以美学值(一个整数)0。在上述例子中，花瓶与花束件：1≤F≤100，F≤V≤100，－50≤AIJ≤50AIIIJ中的美学值。输入整数F，V和矩阵(AIJ)，输出最大美学值和每束花摆放在各个花瓶中的花瓶。 │杜鹃花│7│23-5-2416 │ │- │ │ │康乃馨│-21│5│-4│-20│20第一行包含两个数：F，VFV个整数，Aij即为输入文件中第（i+1）行中的第j个数包含两行:F个数表示摆放方式，即该行的第K个数表示花束K所在的花瓶的。3723–5–24521-410-215-4-2024 很容易想到一个贪心的策略：找到一个符合条件（第i束花要放i-1束花的后面）下的 │ │- │ │ jii个瓶中的一个最大的美学价值在加上当前第ijOPT[I，J]的 (i<=k<=j-1)为i<=呢？复杂度：状态数O（FV）*转移代价O（V）=O（FV2）a,opt,path:array[0..maxn,0..maxn]oflongint;fori:=1tondoforj:=1tomdofori:=1tondoforj:=1tomdofori:=1tondoforj:=itom-n+idofork:=i-1toj-1ifopt[i-1,k]>opt[i,j]thenfori:=n+1tomifi>0then26Consideranarbitrarysequenceofintegers.Onecanplace+or-operatorsbetweenintegersinthesequence,thusderivingdifferentarithmeticalexpressionsthatevaluatetodifferentvalues.Letus,forexample,takethesequence:17,5,-21,15.Thereareeightpossibleexpressions:17+5+-21+15=17+5+-21-15=-17+5--21+15=17+5--21-15=17-5+-21+15=17-5+-21-15=-17-5--21+15=17-5--21-15=WecallthesequenceofintegersdivisiblebyKif+or-operatorscanbeplacedbetweenintegersinthesequenceinsuchwaythatresultingvalueisdivisiblebyK.Intheaboveexample,thesequenceisdivisibleby7(17+5+-21-15=-14)butisnotdivisibleby5.YouaretowriteaprogramthatwilldeterminedivisibilityofsequenceofNN个数中任意地添加+号或-K整除。可以则打印“Divisible”，否则打印“Notdivisible”(1<=N<=10000,2<=K<=17+5+-21+15=17+5+-21-15=-17+5--21+15=17+5--21-15=17-5+-21+15=17-5+-21-15=-17-5--21+15=17-5--21-15=Thelineoftheinputcontainstwointegers,NandK(1<=N<=10000,2<=K<=100)separatedbyaspace.ThesecondlinecontainsasequenceofNintegersseparatedbyspaces.Eachintegerisnotgreaterthan10000byit'sabsolutevalue.Writetotheoutputfiletheword"Divisible"ifgivensequenceofintegersisdivisiblebyKor"Notdivisible"ifit'snot.ThelineofamultipleinputisanintegerN,thenablanklinefollowedbyNinputblocks.Eachinputblockisintheformatindicatedintheproblemdescription.Thereisablanklinebetweeninputblocks.TheoutputformatconsistsofNoutputblocks.Thereisablanklinebetweenoutput24175-214175-21NotDivisibleA*BmodC=(AmodC*BmodC)modC(A+B)modC=(AmodC+BmodC)modC析只说加法）再求余。这样的读入数据就控制在了1-K到K-1的范围内了。（A+B）modK=0or(A+B)mod如果按数的个数划分阶段，前N-1个数的运算结果MODK看做A，第N个数看作BOKopt[i,(j-a[i]modk)modk]=opt[i- opt[i,(j+a[i]modk)modk]=opt[i- programP2042;a:array[0..maxn]oflongint;opt:array[1..2,-maxk..maxk]ofboolean;vis:array[0..maxn]ofboolean;procedureinit;fori:=1tondofori:=1tondoifa[i]modk=0thenvis[i]:=true;fori:=1tondoa[i]:=a[i]modfori:=2tonifnotvis[i]thenforj:=1-ktok-1doifopt[p1,j]thenopt[p2,(j+a[i])modk]:=true;ifopt[p1,0]thenwrin('Divisible')elsewrin('Notdivisible');forii:=1totimdo点是j，长度是L的两个序列的最优值。（i,j）K（i,j）：除了二维和三维加条件外，还可以用i,j,k,t组合来描述一个矩形，滚动数组，滚动数组面也提到过，其实很简单，如果一个状态的决策的步长为N就只X：=K1，K1：=K2，K2；=K3，K3：=XN=3的下标的滚动，在3.1矩阵问题ING^_^n,（1<=n,<=1000开。0表示该块土地有瑕疵，1表示该块土地完好。40111110111102意一个角都可以，依据个人）,长度为K的正方形是否合理，再找到一个K值最大的合法状态就可以了（true表示合理，false表示不合理。其实这就是递推，（决策唯一。如果这个左上角是1呢？如果这三个方向合理的最大边长中一个最小的是XX+1。为什011111111101011110114（2，3（opt[1,3,2]=opt[1,4,1andopt[2,3,1andopt[2,4,1anda[1,3]=1true成立 fori:=1tondoforj:=1tomdofori:=ndownto1doforj:=mdownto1doifa[i,j]<>0thenifopt[i,j+1]<opt[i,j]thenifopt[i+1,j+1]<opt[i,j]thenfori:=1tondoforj:=1tomdoifopt[i,j]>ansthenans:=opt[i,j];AB点。在走过的，他可以取走方格中的数（取走后的方格中将变为数字N（N*N的方格图示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。8 002030020300200002000020200202000020000200002000020020200202大值。显然决策有4中（乘法原理一个点两种*另一个点的两中） 1】programfgqs;a:array[0..maxn,0..maxn]oflongint;opt:array[0..maxn,0..maxn,0..maxn,0..maxn]oflongint;untili=0;functionmax(x,y:longint):longint;ifx>ythenmax:=x;fori1:=1tondoforj1:=1tondofori2:=i1tonforj2:=1toj1if(i1=i2)and(j1=j2)thenelseif(i1=i2-1)and(j1=j2)thenelseif(i1=i2)and(j1=j2+1)else仔细分析发现，处于，同列的状态，等价于另外一个点在对角线上的状态。而N皇的同学一定知道怎么表示右上到左下的这几条对角线，不知道的同学也没关系,对2到N*2。i1,i2的两条路径所取得的数的最大和。a:array[0..maxn,0..maxn]oflongint;untili=0;functionmax(x,y:longint):longint;ifx>ythenmax:=x;fork:=2ton*2dofori1:=1tonif(k-i1>0)and(k-i1<=n)thenfori2:=1tondoif(k-i2>0)and(k-i2<=n)thenifi1=i2elsebegin规划入门30叉数的原因。（当然，如果问题是求所有的和，就没必要转化了，如URALP1039没有G:存图，F[i]表示第i个结点的儿子应该的位W：结点的值BT：二叉树fori:=1tonforj:=1tondoIfg[i,j]then F[i]=0then （l,2,3,…,n号。每个节点都有一个分数（均为正整数idi，tree及它的每个子树都有一个加分，任一棵subtree（也包含tree本身）的加分计算方法如下：。（n＜301004,0,0,00第2行：n个用空格隔开的整数，为该树的前序遍历。557123124subtree的左的加分×subtree的右的加分＋subtree的根的分数枚举树根i那么1，2……i-1就是它的左中的结点，i+1……N就是它右中的结点。这样一颗树按这样的低归定义就构造出来了当然只要这个过程并不需要这棵树。 opt[L,r] programbinary;a:array[0..maxn]oflongint;path,opt:array[0..maxn,0..maxn]oflongint;fori:=1tondoifopt[L,r]=0thenifL>relseifL=rthenelsefori:=Ltordoifx>opt[L,r]thenprocedureprint(L,r:longint);ifpath[L,r]>0thenwrite(path[L,r],'');30ABinaryAppleTree苹果二叉树来源：URALP1018Let'simaginehowappletreelooksinbinarycomputerworld.You'reright,itlooksjustlikeabinarytree,i.e.anybiparousbranchsplitsuptoexactlytwonewbranches.Wewillenumeratebynaturalnumberstherootofbinaryappletree,pointsofbranchingandsoftwigs.Thiswaywemaydistinguishdifferentbranchesbytheirendingpoints.Wewillassumethatrootoftreealwaysisnumberedby1andallnumbersusedforenumeratingarenumberedinrangefrom1toN,whereNisthetotalnumberofallenumeratedpoints.ForinstanceinthepicturebelowNisequalto5.Hereisanexampleofanenumeratedtreewithfourbranches:必须区分不同的枝（结点假定树根都是定为1，并且所用的自然数为1到N。N为所有根和枝的总数。例如