程序设计实习实验班2017作业(算法 作业1, 5)

2017年3月27日4,2625

「Bailian4115」鸣人和佐助

bfs的时候多一维记录查克拉

「poj1190」生日蛋糕/泰国佛塔

从下往上一层一层搜索,每一层枚举半径和高度(注意范围)

根据每一层半径和高度严格递减,进行一些剪枝:

1、剩下的若干层都放最小的圆柱,体积也不够

2、剩下的若干层都放最小的圆柱,得出的表面积比当前最优解劣

3、剩下的体积所需的最小表面积加上当前表面积比当前最优解劣

「Bailian4119」复杂的整数划分问题

令F1(i, j)为把i划分成j个正整数的方案数

1.划分出一个1,\(F1(i+1, j+1) += F1(i,j)\)

2.将当前所有划分加1,\(F1(i+j,j) += F1(i,j)\)

令F2(i, j)为把i划分成j个不同正整数的方案数

1.将当前所有划分加1,并划分出一个1,\(F2(i+j+1, j+1) += F2(i,j)\)

2.将当前所有划分加1,\(F2(i+j,j) += F2(i,j)\)

令F3(i, j)为把i划分成j个奇正整数的方案数

1.划分出一个1,\(F3(i+1, j+1) += F3(i,j)\)

2.将当前所有划分加2,\(F3(i+j+j,j) += F3(i,j)\)

热血格斗场

经典set的应用

「poj1290」Blocks

先将相邻的同色块合并,记忆化搜索

F(l, r, len)表示将l到r消去的最大得分,此时r之后有一段长为len的方块与r同色

转移1:将r和len一起消除

转移2:在l到r-1中枚举一个和r同色的段i,那么i到r之间的就内部解决,即\(F(i + 1, r – 1, 0)\),和另一段\(F(l, i, num_r + len)\)

「poj1191」棋盘分割

维护二维前缀和,记忆化搜索

「poj1724」ROADS

用F(i,j)表示花费为i,走到点j的最短路

按照花费分层转移即可

01:List

02:RPN Calculator

03:Set

04:字符串操作

每次读入一个词之后,判断末尾的若干个词是否是一次操作,处理操作压栈

check 用于判断某个单词是否是操作

count 用于找到离末尾最近的一个操作

05:热血格斗场

06:冷血格斗场

07:priority queue练习题

08:编程填空:数据库内的学生信息


 

说点什么

提醒
avatar
PM
PM

黄学长,能详细解释一下字符串操作的代码吗 实在看不懂 Orz

orz

学长,这些题目您在高中就已经会做,为什么上大学还要学这个