noip中常见的典型例题.pdf

NOIP中常见的典型例题陈启峰整理叠叠 放放 箱箱 子子• 【【问题问题】】 •某港口有一批箱子，将其编号，分别为1至N每一个箱 子的尺寸规格是一样的，现在要将其中某些箱子叠放起来， 箱子叠放的规则如下： • 一、每个箱子上最多只能直接叠放直接叠放一个箱子； • 二、编号较小的箱子不能放在编号较大的箱子之上； • 三、每个箱子都给出了自身重量自身重量与可承受重量可承受重量，每个箱子 之上的所有箱子重量之和不得超过该箱的可承受重量 •为了节约堆放场地，希望你编程从中选出最多最多个箱子， 使之能够在满足条件的情况下叠放起来• 【【输入输入】】 •第一行是一个整数N（1≤N≤1000） •以下共有N行，每行两个整数，中间以空 格分隔，分别表示每个箱子的自身重量与 可承受重量，两个数值均为小于等于3000 的正整数 • 【【输出输出】】 •第一行应当输出最多可叠放的箱子总数M样例样例】】 有五个箱子，如下表：编号自身重量 可承受重量119152713357468512则最多 可以叠 放4个 箱子， 方案之 一如： 1、2、 3、5分析•设F[i,j]表示第i个箱子到第N个箱子中总重量为j的 最大箱子数。

• 考虑第i个箱子放与不放的情况• 注意，能选的条件是 • j ≥ weight*i+ 并且capacity≥j-weight[i]selectselectnot 1]][, 1[], 1[max],[  iweightjiFjiFjiF代码•program CQF_BOX;program CQF_BOX; •uses math;uses math; •const maxn=1000;const maxn=1000; •var weight,capacity:array[1..maxn] of longint;var weight,capacity:array[1..maxn] of longint; •f:array[1..maxn+1,0..6000] of longint;f:array[1..maxn+1,0..6000] of longint; •n:longint;n:longint; •procedure init;procedure init; •var i:longint;var i:longint; •beginbegin •readln(n);readln(n); •for i:=1 to n dofor i:=1 to n do •readln(weight[i],capacity[i]);readln(weight[i],capacity[i]); •end;end;•procedure work;procedure work; •var i,j,ans:longint;var i,j,ans:longint; •beginbegin •fillchar(f,sizeof(f),200);fillchar(f,sizeof(f),200); •f[n+1,0]:=0;f[n+1,0]:=0; •for i:=n downto 1 dofor i:=n downto 1 do •for j:=0 to 6000 do beginfor j:=0 to 6000 do begin •f[i,j]:=f[i+1,j];f[i,j]:=f[i+1,j]; •if (j>=weight[i])and(capacity[i]>=jif (j>=weight[i])and(capacity[i]>=j- -weight[i]) thenweight[i]) then •f[i,j]:=max(f[i,j],f[i+1,jf[i,j]:=max(f[i,j],f[i+1,j- -weight[i]]+1);weight[i]]+1); •end;end; •ans:=0;ans:=0; •for i:=0 to 6000 dofor i:=0 to 6000 do •ans:=max(ans,f[1,i]);ans:=max(ans,f[1,i]); •writeln(ans);writeln(ans); •end;end;CMI• 给出一个1到n的排列，每次可以移动一个 数到一个任意位置。

问要达到状态1,2,3……n 至少移动多少次？ • Sample Input • 5 • 2 1 4 5 3 • Sample Output • 2分析• 答案就是N减去这个排列的最长上升子序列 的长度lis• 为什么呢？证明• 必要性：• 一次移动就相当于删除一个数并添加上这 个数 • 删除一个数不会增加lis • 添加一个数最多使lis加1 • 因此一次移动最多可以使lis加1 • 要达到目标状态至少要N-lis次移动证明• 充分性： • 每次选取一个非lis上的一个数，并将它移动 到lis上合适的位置也就是说，将它移动到 lis上前比它小，后比它大的位置算法• 运用动态规划： • F[i]表示以第i个数为结束的最长上升子序列 的长度 • F[i]=max{F[j]+1|value[j]last[lis] then begin •inc(lis); •last[lis]:=value[i]; •end •else •update(0,lis); •writeln(n-lis); • end;• procedure update(a,b:longint); • begin •if a=b then •last[a]:=value[i] •else •if last[(a+b)shr 1]>value[i] then •update(a,(a+b)shr 1) •else •update((a+b)shr 1+1,b); • end;寻宝游戏寻宝游戏• 游戏中的提示都由数列组成，而“藏宝图”则是一个 N×M个数的表格。

只要找出数列与表格的“接近程度”， 就找到了当前位置与宝藏埋藏点的距离接近程度”的 定义为：假设提示数列为{ai}，那么“藏宝图”中找出与 其最为接近的数列{bi}(数列项数同为Len)，这两数列的接 近程度就是数列与表格的接近程度，其中数列的接近程度 D=∑(ai-bi)2(i∈[1,Len])，D越小就表示越接近除此以外，数 列{bi}还有以下的限制：用(xi,yi)表示数列{bi}中第i项在表格 中的位置，则要求|xi-xi+1|+|yi-yi+1|=1(i∈[1,len-1]))，且同一 位置可能在数列中出现多次 • 为获得此大奖，你需要编写一个程序，求出表格和数列的 接近程度 • 序得出数列与表格的接近程度寻宝游戏寻宝游戏•SAMPLE INPUT •5 5 •0 0 0 1 0 •1 0 0 0 0 •0 1 0 0 0 •0 0 0 2 0 •0 0 0 0 0 •6 •1 0 1 2 1 1 •SAMPLE OUTPUT •3 •数据范围 •2≤N、M≤100，1≤Len≤250表格和数列中的每一项都小于100分析• 设F[i,x,y]表示ai与表格中位于(x,y)的数向对 应，且数列{ai}的前1～i-1项与表格中所有bi 位置为(x,y)的数列的最小接近程度。

• B1和B2~Bn是有点不一样的 • 因为B2~Bn都和前面的数有位置关系，而B1 没有 • 所以初始化条件为 • F[1,x,y]=(a[1]-table[x,y])2分析• 转移方程• 答案就是min{F[len,x,y]}    ] 1,, 1[], 1, 1[] 1,, 1[], 1, 1[min]),[][(],,[2yxiFyxiFyxiFyxiFyxtableiayxiF代码•program CQF_TREASURE;program CQF_TREASURE; •uses math;uses math; •var a:array[1..250] of longint;var a:array[1..250] of longint; •table:array[1..100,1..100] of longint;table:array[1..100,1..100] of longint; •f:array[1..250,0..101,0..101] of longint;f:array[1..250,0..101,0..101] of longint; •n,m,len:longint;n,m,len:longint; •procedure init;procedure init; •var i,j:longint;var i,j:longint; •beginbegin •readln(n,m);readln(n,m); •for i:=1 to n dofor i:=1 to n do •for j:=1 to m dofor j:=1 to m do •read(table[i,j]);read(table[i,j]); •readln(len);readln(len); •for i:=1 to len dofor i:=1 to len do •read(a[i]);read(a[i]); •end;end;代码•procedure work;procedure work; •var i,j,k,ans:longint;var i,j,k,ans:longint; •beginbegin •fillchar(f,sizeof(f),45);fillchar(f,sizeof(f),45); •for i:=1 to n dofor i:=1 to n do •for j:=1 to m dofor j:=1 to m do •f[1,i,j]:=sqr(a[1]f[1,i,j]:=sqr(a[1]- -table[i,j]);table[i,j]); •for i:=2 to len dofor i:=2 to len do •for j:=1 to n dofor j:=1 to n do •for k:=1 to m dofor k:=1 to m do •f[i,j,k]:=sqr(a[i]f[i,j,k]:=sqr(a[i]- -table[j,k])+min(f[itable[j,k])+min(f[i- -1,j1,j- - 1,k],min(f[i1,k],min(f[i- -1,j,k1,j,k- -1],min(f[i1],min(f[i- -1,j+1,k],f[i1,j+1,k],f[i- -1,j,k+1])));1,j,k+1]))); •ans:=maxlongint;ans:=maxlongint; •for i:=1 to n dofor i:=1 to n do •for j:=1 to m dofor j:=1 to m do •ans:=min(ans,f[len,i,j]);ans:=min(ans,f[len,i,j]); •writeln(ans);writeln(ans); •end;end;数字游戏•小W发明了一个游戏，他在黑板上写出了一行 数字a1，a2，a3，……，an，然后给你M个回合的 机会，每回合你可以从中选择一个数字擦去它， 接着剩下来的每个数字ai都要递减一个值bi。

如此 重复m个回合，所有你擦去的数字之和就是你所 得的分数 •小W和他的好朋友小Y玩了这个游戏，可是他 发现，对于每个给出的a和b序列，小Y的得分总比 他高，所以他就很不服气于是他想让你帮他算 算，对于每个a和b序列，可以得到的最大得分是 多少数字游戏• 输入文件： •输入文件的第一行是一个整数n （11)and(heap[son div 2]>heap[son]) do •begin •tmp:=heap[son div 2]; •heap[son div 。