描述
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。
格式
输入格式
输入n，k (6<n<=200，2<=k<=6)
输出格式
一个整数，即不同的分法。
样例1
样例输入1
7 3
样例输出1
4
限制
每个测试点1s
来源
NOIP2001第二题
继续阅读
Vijos 数的划分 题解
发表评论
分类目录归档：动态规划
NOIOJ 比赛排名 题解
Openjudge Charm Bracelet
Charm Bracelet
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charmiin the supplied list has a weight Wi(1 ≤ Wi≤ 400), a ‘desirability’ factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
- 输入
- Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di - 输出
- Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
- 样例输入
-
4 6 1 4 2 6 3 12 2 7
- 样例输出
-
23
- 来源
- USACO 2007 December Silver
Openjudge 复杂的整数划分问题
复杂的整数划分问题
- 总时间限制:
- 200ms
- 内存限制:
- 65536kB
- 描述
- 将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。 - 输入
- 标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。
(0 < N <= 50, 0 < K <= N) - 输出
- 对于每组测试数据，输出以下三行数据:
第一行: N划分成K个正整数之和的划分数目
第二行: N划分成若干个不同正整数之和的划分数目
第三行: N划分成若干个奇正整数之和的划分数目 - 样例输入
-
5 2
- 样例输出
-
2 3 3
- 提示
- 第一行: 4+1, 3+2,
第二行: 5，4+1，3+2
第三行: 5，1+1+3， 1+1+1+1+1+1
Openjudge 最佳加法表达式 题解
最佳加法表达式
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 给定n个1到9的数字，要求在数字之间摆放m个加号(加号两边必须有数字），使得所得到的加法表达式的值最小，并输出该值。例如，在1234中摆放1个加号，最好的摆法就是12+34,和为36
- 输入
- 有不超过15组数据
每组数据两行。第一行是整数m，表示有m个加号要放( 0<=m<=50)
第二行是若干个数字。数字总数n不超过50,且 m <= n-1 - 输出
- 对每组数据，输出最小加法表达式的值
- 样例输入
-
2 123456 1 123456 4 12345
- 样例输出
-
102 579 15
- 提示
- 要用到高精度计算，即用数组来存放long long 都装不下的大整数，并用模拟列竖式的办法进行大整数的加法。
- 来源
- Guo Wei
极其坑爹的一道题！要写高精度！坑人！
继续阅读
Openjudge Zipper
Zipper
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order.
For example, consider forming “tcraete” from “cat” and “tree”:
String A: cat
String B: tree
String C: tcraeteAs you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming “catrtee” from “cat” and “tree”:
String A: cat
String B: tree
String C: catrteeFinally, notice that it is impossible to form “cttaree” from “cat” and “tree”.
- 输入
- The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line.
For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive.
- 输出
- For each data set, print:
Data set n: yes
if the third string can be formed from the first two, or
Data set n: no
if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example.
- 样例输入
-
3 cat tree tcraete cat tree catrtee cat tree cttaree
- 样例输出
-
Data set 1: yes Data set 2: yes Data set 3: no
- 来源
- Pacific Northwest 2004
继续动规：
继续阅读
Openjudge 拦截导弹 题解
拦截导弹
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。
- 输入
- 输入有两行，
第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），
第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。 - 输出
- 输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。
- 样例输入
-
8 300 207 155 300 299 170 158 65
- 样例输出
-
6
- 来源
- 医学部计算概论2006期末考试题
简单动态规划：
继续阅读
Openjudge 爬楼梯 题解
3089:爬楼梯
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数
例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级
也可以第一次走两级，第二次走一级，一共3种方法。
输入
输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30
输出
不同的走法数，每一行输入对应一行输出
样例输入
5
8
10
样例输出
8
34
89
这个好像就有点类似于动态规划的感觉咯。但是其实这还是动规里最简单的题。但是初学感觉有点难度了。233
继续阅读
MOOC学习递归中涉及动态规划部分经典题目
2017-07-14更新放苹果问题：参考http://www.cnblogs.com/wxgblogs/p/5742618.html
放苹果
设函数f(M,N)为把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放的分法的数量。（5，1，1和1，5，1 是同一种分法。）
求该函数的递推式
解答：
f(m,n)={
m==0||n==1 -> 1;
m
m>=n -> f(m-n,n) + f(m,n-1); //分成两种情况，f(m-n,n)是没有空盘子：把n个盘子里每个都装上一个苹果，剩下的m-n个苹果再装到n个盘子里；f(m,n-1)是有空盘子，把那一个不装扔出来就好。
}
简单的整数划分问题
将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。设函数f(m,n)为将整数m划分为每个数最大为n的划分数。
求该函数的递推式
解答：
f(m,n)={
m==1|| n==1 -> 1; //m==1时，只能分成1个1；n==1时,只能分成m个1。
m
m==n -> 1+f(m,n-1); //当m==n时，因为整数m可以自己算作一个划分，那么就要把n-1传递下去
m>n -> f(m-n,n)+f(m,n-1); //m>n时，可以在当前状态下分出去n或者不分出去n，对应两个f();
}
分解因数
给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 * a2 * a3 * … * an，并且1 < a1 <= a2 <= a3 <= ... <= an，问这样的分解的种数有多少。注意a = a也是一种分解。
解答：设函数f(m,n)为将整数m划分成小于等于整数n的划分数。
f(m,n)={
n==1 -> 0; //划到1就不能再往下分了
m==1 -> 1;
m%n==0 -> f(m/n,n) + f(m,n-1); //当m可以整除n的时候，可以除完了划分下去，也可以不除
m%n!=0 -> f(m,n-1); //只能不除
}