集训队作业-汤泽解题报告

AnudnikTimeLimit:1.0secondMemoryLimit:1000"Iftwopeoplewerebornoneafteranotherwithoneseconddifferenceandoneofthemisachild,thentheotheroneisachildtoo.Wegetbyinductionthatallthepeoplearechildren."EveryoneknowsthatthemathematicaldepartmentoftheUralStateUniversityisabigfamilyofN s,1,2,3,...,NyearsoldOncethedeanofthedepartmentorderedaphotoifhisbigfamily.Thereweretobepresentallthestudentsofthedepartmentarrangedinonerow.Atthedeanwantedtoarrangethembytheiragestartingfromtheheadvisedtoarrangethestudentsasfollows.The1yearoldstudentistositattheleftendoftheThedifferenceinagesofeverytwoneighborsmusexceedThedeandecidedthattherebythestudentswouldseemlookastheywerearrangedbytheirages(onecanhardlyseethedifferenceinagesof25and27yearsoldpeople).Thereexistseveralarrangementssatisfyingtotherequirements.Photographerdidn’twanttothwartdean’sdesireandmadethephotosofallthepossiblemathematicaldepartmentstudents’ThereistheintegernumberN,thenumberofphotosmadebytheSample4Sample4IfN=4thentherearefourpossiblearrangements:(1,2,3,4),(1,2,4,3),(1,3,2,4)and(1,3,4,2).试题简介（URAL1260：（1）1（2）2。稍微分析一下就会发现，枚举肯定是不可行的，只能通过寻找规律来为了考虑方便，先假定N那么对于一个满足条件的方案，前三个数的排列只有可能是（12X（12（134（135）这四种情况。来逐个分析这四个情况X：满足条件，为N-1时的案。反过来考虑，对于任意一个N-1的方案，将N-1个数都加上1，并在序列的左边补上一个1，此时又变成了一个N的方案。因此，开头为（12X）的N的方案和N-1（132：去掉（132）后，剩下的N-33，就得到了一个N-3方案类似的任意一个N-3的方案所有数加上3，并在序列左边补（132就得到一个N（132）NN-3（134：因为最初假定了N比较大，而能2相邻的数都已经放好，因2只能放在4的后面。此时最小的数为5，它仍然比23，因此只N=45：2（24664（3。654以证明，86897这种规律不断地放数，不难证明，如果是以135开头，只存在案：137……8642F[1]=1，F[2]=1，F[3]=2，F[N]=F[N-1]+F[N-3]+1{$r-,s-,q-const = = =varf :array[1..maxn]ofextended; :integer;procedureinit;{assign(input,infns);{close(input);}proceduremain;{递推过程}vari :integer;f[1]:=1;f[2]:=1;f[3]fori:=4tondof[i]:=f[i-