学术派 | 对于蓝竹笋的初步研（乱）究（搞）

某一天当我还是个萌新，在东北玩泥巴雕塑园看着攻略连馒头的时候，突然

于是我陷入了深深的撕烤，哦不，思考【然后就把这事儿给鸽了，对方可是蓝莓啊喂@Amastacia 大佬我错了

我要讲啥来着、、、哦利用动态规划解决问题

具体是什么问题呢：造竹笋 by 这位蓝莓

本人画图可好啦！于是画了个二重竹笋卖个萌

显然对于竹笋，给出一个图案，一定是能按照一定顺序连出来的，因此顺序并不重要。重要的是，怎么连【凑字数的废话。

好，先来看一个naive的问题：n重竹笋要多少个portal？

然后蓝莓的要求是

以下为技【cou】术【zi】部分：

Sol1.

假设每个portal的坐标已经确定，不妨先设刚好有 n=124 个点，且能够组成一个六重竹笋。

评价：好像并没有什么卵用，五重应该还能用上来凑凑数

Sol2.

介于 @Amastacia 自己的行动四层蓝竹笋已经覆盖了大半个北航校园可知无用点应当相当多，因此需要一个比较简单却高效的剪枝

Step1.首先计算每个三角形内有多少po：

这就可以转化成一个简单的二维坐标系某个点左下方有几个点的问题，

Step2. 接下来就可以瞎搞了

（我猜的）

Step3. 愉快的压常数

n=5的时侯，对于每一个点pp，建立矩阵M，

这些(i,j,k)即所有五重竹笋的外点

对于每一行，都可以用压成一个大整数，因此单次操作的时间复杂度为

综上。。。总算是搞完了。。理论复杂度在n=200n=200的时候大概能做

而最少的n=124即可做一个六重蓝竹笋，算法复杂度还是很可观的

（编辑：这是编辑的最痛苦的几篇稿子之一……实在搞不定上图了！原文载于rausen的博客，点击阅读原文跳转）

欢迎登陆北京ingress抵抗军官网

历史文章请访问 https://bjres.net  查看