NOIP2010年提高组结题报告.doc

题目描述 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。假设内存中有M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M?；；1，软件会将新单词存入一个未使用的内存单元；若内存中已存入M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。假设一篇英语文章的长度为N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。【数据范围】对于10%的数据有M=1，N≤ 5。对于100%的数据有0M≤ 100，0N ≤ 1000。 输入格式 in，输入文件共2 行。每行中两个数之间用一个空格隔开。第一行为两个正整数M 和N，代表内存容量和文章的长度。第二行为N 个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。 输出格式 共1 行，包含一个整数，为软件需要查词典的次数。 【输入输出样例1】 3 7 1 2 1 5 4 4 1 【输入输出样例2】 2 10 8 824 11 78 11 78 11 78 8 264 【输入输出样例1】 5 【输入输出样例2】 6 初拿这道题感觉很简单，不就是模拟嘛，亏我还先做的第二道题。这道题完全可以用队列 来模拟；不过这道题一定要注意，队列出队的问题，当满队的时候，如何处理？这里我是边 读边处理完全可以的；我们可以设数组c来控制队列，数组b来当作字典；t来记录查找次 数；x是单词数，与m一起控制队列，即当xm时，表示已满单词数，当前单词需要另外储存；好了，模拟算法出来了：实现如下： (AC) program p1067; var m,n,x,t,a,i:longint; b:array[1..1000] of boolean; c:array[1..1000] of longint; begin readln(m,n); t:=0; x:=0; for i:=1 to n do begin read(a); if b[a] then continue; inc(x); c[x]:=a; b[a]:=true; inc(t); if xm then b[c[x-m]]:=false; end; writeln(t); end. 题目:[NOIP2010]乌龟棋 问题编号:599 题目描述 小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 输入格式 输入文件的每行中两个数之间用一个空格隔开。第1 行2 个正整数N 和M，分别表示棋盘格子数和爬行卡片数。第2 行N 个非负整数，a1, a2, ……, aN，其中ai 表示棋盘第i 个格子上的分数。第3 行M 个整数，b1,b2, ……, bM，表示M 张爬行卡片上的数字。输入数据保证到达终点时刚好用光M 张爬行卡片，即N?；；1=Σb_i (1=i=M) 输出格式 输出只有1 行，1 个整数，表示小明最多能得到的分数。 【输入输出样例1】 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1 【输入输出样例2】 13 8 4 96 10 64 55 13 94 53 5 24 89 8 30 1 1 1 1 1 2 4 1 【输入输出样例1】 73 【输入输出样例2】 455 当拿到这套题的时候，我首选做的这道题，完全可以把卡片费用，格子上分数作为物品； OK，动规出来了。可是动规方程该怎么办，费了好多的周折，甚至想到了把这两种物品从 新定义；甚至把格子个数作为费用，卡片作为物品，这样处理来求一个最大值……想了好长 时间啊，但那样根本没办法进行动规，因为卡片是有限的，还有一点要注意就是用了之后就 没了……啊，想到这里，初思路了，注意题上就给四种卡片，我们可以设一个四维数组来一 个四维动规嘛，好吧！方程出来了： f[i,j,k,l]:=max(max(f[i-1,j,k,l],f[i,j-1,k,l]),max(f[i,j,k-1,l],f[i,j,k,l-