passzh
- 浏览: 20617 次
- 性别:
- 来自: 上海
-
最新评论
文章列表
在动态规划中，有一类经常出现的问题，即0-1背包问题。所谓0-1背包问题，即有n个物品，其每个背包的价值为vi(1<=i<=n),每个物品的重量为wi(1<=i<=n),背包能够放的总重量为c，求放哪几个物品使得物品的总价值最大。
很明显，物品要么放进背包，要么不放进。故称为0-1背包。
我们假设放进了m个物品{x1,x2,...,xm},那么它是满足最优子结构的，即如果这是问题的最优解，那么{x2,...,xm}一定是问题c-wx1的最优解。所以，这道问题可以用动态规划进行求解。
我们可以定义一个数组m[i][j],用它表示背包容量为j，可选物品为i,i+1,...,n ...
题目的链接为：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1028
题目为：
Digital Roots
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:329 测试通过:112
描述
The digital root of a positive integer is found by summing the digits of the integer. If the resulting ...
《偶得》
风吹杨柳飘轻絮，雨打春江满目愁。
两处相思催人老，转眼青丝尽白头。
《落花》
庭院深深伴孤身，清酒月下忘世纷。
醉卧芍药不觉晓，一夜红泪尽沾身。
《桃源》
幽涧曲径何处访，清月千年笼寒沙。
东晋仙翁应不在，辜负流水待落花。
《浮生如梦》
坐听风吹竹，笑看暮合昏。
醉眼观世事，杯酒祭乾坤。
《夜雨》
寒雨打窗楞，凉意入薄衾。
孤枕梦难成，一夜到天明。
《红梅》
点点猩红染虬枝，冷香徐放报春知。
傲雪凌寒铮铁骨，何惧风雪夹击时。
《景》
萧风凄清湘水寒，雾霭迷蒙月色残。
冷涛幽咽轻推岸，多情谁人独凭栏。
题目的链接为：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1022
题目的描述为：
哈夫曼编码与译码
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:343 测试通过:123
描述
...
题目的地址：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1021
题目的描述：
二叉树复制和左右子树互换
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:272 测试通过:174
...
题目的链接为：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1017
题目的描述为：
乘积最大
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:228 测试通过:100
描述
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所 ...
Today I have read a unbelievable news that less sleep may leads to gain more fat. In traditional opinon,a man who usually feel fatigue and do many works may looks very thin. The news points out that the sleep habit may affects a man's look including his weight.
So I must persist sleep more than 7 hou ...
题目的链接：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1010
题目的描述：
数的计算
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:531 测试通过:162
描述
要求找出具有下列性质数的个数（包含输入的自然数n）：
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1. 不作任何处理;
2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
...
题目的链接为：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1009
题目为：
2的N次方
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:999 测试通过:500
描述
编程精确计算2的N次方。（N是介于100和1000之间的整数）。
输入
正整数N (100≤N≤1000)
输出
2的N次方
样例输入
200
样例输出
16069380442589902755 ...
题目的链接为：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1008
题目为：
第几天
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:899 测试通过:237
描述
在我们现在使用的日历中, 闰年被定义为能被4整除的年份，但是能被100整除而不能被400整除的年是例外，它们不是闰年。例如：1700, 1800, 1900 和 2100 不是闰年，而 1600, 2000 和 2400是闰 ...
题目的链接为：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1006
题目为：
多项式乘法
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:171 测试通过:77
描述
线性表是一 ...
题目的链接为http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1005
题目如下：
多项式加法
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:964 测试通过:100
描述
线性表是一种最简单、最基本，也是最常用的数据结构，其用途十分广泛，例如，用带表头结点的单链表求解一元整系数多项式加法和乘法运算。
现给两个一元整系数多项式，请求解两者之和。
输入
两组数据，每一组代表一个一元整 ...
题目的链接地址为：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1004
题目为：
线性表操作
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:1610 测试通过:340
描述
线性表是n个元素的有序集合（n³0），n是线性表中元素的个数，称为线性表的长度。可以用一组地址连续的存储单元依次存储线性表中元素，采用这种存储方式的线性表称为顺序表。
请在顺序表上实现运算，实现顺序表的逆置，删除 ...
POJ1611解题报告
- 博客分类：
- 并查集
The Suspects
Time Limit: 1000MS Memory Limit: 20000K
Total Submissions: 14274 Accepted: 6780
Description
Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strate ...
并查集是一种比较有用的数据结构，主要是用于解决将一些元素合并和查找元素在某个集合的操作，即union操作和findSet操作。
其中，利用有根树实现并查集的方法是普遍使用的方法，也是效率最优的方法。
在并查集一开始时， ...