Ubuntu 指路贴 – Part 0

又是一个三天小长假,来写点东西。上一次五一长假写了篇关于jokebird机器人的东西 开坑!写一个Jokebird机器人——一点扯淡 开坑!写一个Jokebird机器人——底层模拟 开坑!写一个Jokebird机器人——js替换 ...

天上掉Pizza DP

题解 同样状压dp t[sta][i]表示在sta状态时购买了i号pizza所得到的折扣 预处理和答案统计就不多废话了 CODE [crayon-6002c5fa46b97182190426/] 问题 C: 天上掉Pizza 时间限制: 3 Sec  内存限...

加分二叉树 DP

题解 因为中序遍历顺序为左根右,因此转化为在一段区间内作为一个子树,从中选一个点作为根,计算出这段区间的的最大分数。 因为要输出前序遍历所以要记录这个区间里那个点是根,然后递归输出。 因为行末...

最大的算式 动态规划

题解 预处理前缀和 f[i][k]表示前i个数字之间插入k个括号时的最大值(k<i) 初始 f[i][0]=a[i]; 转移 枚举 i:前i个数字 (当前问题) k:插入k个乘号(k<i) j:第k个乘号所在位置 f[...

炮兵阵地 状压DP

题解 读入好像有那么一些些问题 f[i][sta1][sta2]表示第i行为sta2且前一行为sta1时的最大值 预处理:同一行的状态,上下两行的可行状态 f[i][sta1][sta2]=max(f[i-1][sta][sta1]+v[sta2]) CODE [cray...

稀有矿井 状压DP

题解 树形dp+状压 f[i][sta]表示第i个节点拥有的矿石种类为sta时的最小花费(sta[i]=1既拥有第i种矿石) 初始 f[i][1 << (m - 1)]=0 (i有m种矿石) f[i][0]=0 转移 先计算子树的f,再合成根的f...

导游2 状压DP

题解 这里全写成了记忆化搜索 f[i][sta]表示前i个人对应景点状态sta时的最大值(sta[i]=1则为已分配) 为第i个人分配时遍历sta的每一位,为0就分配然后往下走 注意高低位,运算级什么的 CODE [crayon-6...

NOI1995 石子合并 DP+平行四边形优化

题解 维护前缀和,枚举分割点k dp[i][j]表示第i到第j堆石子合并的最优值,sum[i][j]表示第i到第j堆石子的总数量。 平行四边形优化 设m[i,j]表示动态规划的状态量。 m[i,j]有类似如下的状态转移...

小明的喷漆计划 DP

[latexpage] 题解 貌似写的太复杂了 先对原字符串预处理,使得任意两相邻块颜色不同 aaaabbbaaa-->aba f[i][j][c]表示将i~j涂为c颜色所用最小次数 初始 \[\begin{array}{l} f[i][i][c] = 1(...

tyvj1193 括号序列 DP

[latexpage] 题解 f[i][j]表示将i~j转化为合法序列最少用的括号数 若st[i]和st[j]匹配,f[i][j]可以是f[i+1][j-1]; 再枚举分割点k \[f[i][j] = MIN(f[i][j],f[i][k] + f[k + 1][j])(i \le k \le j - 1...