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

2017年3月27日2,1805

【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:编程填空:数据库内的学生信息


 

  • orz2017年6月13日 下午4:50 回复

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

    #1  
    • admin2017年6月15日 下午10:53 回复
      admin

      OwO 复习复习丫

      #11
  • PM2017年6月23日 下午5:44 回复

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

    #2  
    • admin2017年6月24日 上午11:29 回复
      admin

      已经添加

      #21
      • PM2017年6月25日 下午2:31 回复

        非常感谢ヾ(≧▽≦*)o

        #22