dp的入门题目.doc

1．抢金块(gold) 【问题描述】 地面上有一些格子，每个格子上面都有金块，但不同格子上的金块有不同的价值，你一次可以跳S至T步(2≤S＜T≤10)。例如S=2，T=4，你就可以跳2步、3步或4步。你从第一个格子起跳，必须跳到最后一个格子上，请你输出最多可以获得的金块的总价值。 【输入格式】 第一行是格子个数n(n＜1000)；第二行是S和T，保证T大于S(2≤S＜T≤10)； 第三行是每个格子上的金块价值Pi(Pi＜10000)。 【输出格式】 输出最多可以获得的金块的总价值。 【输入样例】 10 2 3 4 5 8 2 8 3 6 7 2 9 【输出样例】 36 样例说明：跳1、3、5、8、10，总价值：4+8+8+7+9=36。 2．维修栅栏(fence) 【问题描述】 农场的栅栏年久失修，出现了多处破损，晶晶准备维修它，栅栏是由n块木板组成的，每块木板可能已经损坏也可能没有损坏。晶晶知道，维修连续m个木板(这m个木板不一定都是损坏的)的费用是sqrt(m)。可是，怎样设计方案才能使总费用最低呢？请你也来帮帮忙。 【输入格式】 第一行包含一个整数n(n≤2500)，表示栅栏的长度；第二行包含n个由空格分开的整数(长整型范围内)。如果第i个数字是0，则表示第i块木板已经损坏，否则表示没有损坏。 【输出格式】 仅包含一个实数，表示最小维修费用；注意：答案精确到小数点后3位。 【输入样例】 9 0 –1 0 1 2 3 0 –2 0 【输出样例】 3.000 3、密码锁 有一个炸弹被敌人设置了密码，现在要求你来破解这个密码！已知密码是由N个数字组成的，并且密码是用下图所示的面板设置的，还知道敌人设置的密码中任意相邻的两个数字在面板中的按键也是相邻的（也就是说两个按键有公共边）。 为了估计大概破解的时间，现在任务是要求你计算一下，敌人设置的密码有多少种不同的可能？ 输入格式： 一个整数N, 2 = N = 30　 输出格式： 一个整数,密码有多少种不同的可能. 输入数据 输出数据 2 26 3 74 25 768478331222 4. fstring字符串 (fstring) 【问题描述】 一个只包含A，B，C三种字符的字符串，如果其中有连续的3个由A，B，C各一个组成的子串，则称这个字符串为fstring字符串。 例如：BAACAACCBAAA 就是一个fstring字符串，而AABBCCAABB则不是。 你的任务就是计算只包含A，B，C三种字符且长度为n的这种字符串有多少个不是fstring字符串。 【输入格式】 一个整数n(1≤n≤30)。 【输出格式】 一个整数。 【输入输出样例】 输入 输出 样例1 2 9 样例2 3 21 5、全排列 把1至N里面所有的正整数排成一列就是一个排列，显然不同的顺序可以有不同的排列，共有N!个不同的全排列。现在有两种询问，一种是询问字典序第几小的是哪个排列，把这个排列输出；另一种询问是给出一个排列，然后问这个排列是第几小的。例如，N = 5，第3小的排列就是1 2 4 3 5，因为1 2 3 4 5是第一小的，1 2 3 5 4是第二小的。同理如果给出一个排列，例如是1 2 5 3 4，那么可以知道它是第5小的。 输入格式： 第一行：两个整数N和K。1=N=20,1=K=10000。 第2至2*K行，每两行描述一个询问。如果是字符‘P’，那么下一行是一个整数X，表示询问第X小的排列是哪个排列，把这个排列输出来，如果是字符‘Q’，那么下一行给出一个排列，你需要判断这个排列是第几小的。 输出格式： 共K行，每行对应一个询问。 输入样例： line.in 5 2 P 3 Q 1 2 5 3 4 输出样例：line.out 1 2 4 3 5 5 样例解释： 有2个询问，第一个询问是第3小的是哪个排列；第二个询问是1 2 5 3 4 是第几小的。