Link 这个题有一个很特殊的点，就是最大值不会超过28，可以想一下最多可以合并多少次。 那么常规的区间dp是不能使用的，就要采用特殊的形式， $dp_{i,j}$ 表示$i$在左边，达到$j$的话的右端点位置 $dp{i,j}=dp{dp_{i,j-1}+1,j-1}$ 然后转移就可以了. #include<cstdio> #incl…

Linkkkkkkkkkkkk 这其实是个dp问题 可以拆成一个个dp小问题，然后求和，这个小问题就是以$(i,j)$为右下角方块下会有多少矩形，然后把每一个位置加起来就行了。 应注意到以下命题充要性成立:如果$(i,j)$位置存在一个正方形长度为n满足题意，那么在$(i-1,j),(i,j-1),(i-1,j-1)$处都应存在着长度为 n-1的矩…

P4302 [SCOI2003]字符串折叠 Jennie 注意，这个题之所以写成带$()$的形式，不是为了解释说明，而是你最后输出的格式。 然后就是水的一批的区间dp #include<iostream> #include<cstdio> #include<cstring> #include<cmath&g…

P5785 [SDOI2012]任务安排 介绍 这个题我们分析一波P5785 [SDOI2012]任务安排 首先这个s很讨厌，不过我们可以把每一个批次的s的影响扔到后面去，对后面的产生而不是前面，然后写出dp方程 $f_i=f_j+s\times (sum_n-sumc_j)+sumt_i\times(sumc_i-sumc_j)$ 然后把只带 $…

Jennie 第一问和第二问分开做比较好 第一问贪心谁都会。 第二问可以用背包的方式求最少移动次数，但不知道为什么我的程序挂了hhh 换种思路，求最少多少水不用动就省事了 注意初始化. #include<cstdio> #include<iostream> #include<cstring> #include&l…

Jennie 谁都能看出来是个背包求方案数，不过问题是怎么求 毕竟这个数据范围太诡异了。 但是背包计数不过是一种递推吧了。 并不容易但唯一的方法是采用矩阵乘法来加速 然后开一个100*100的矩阵开始递推。 #include<cstdio> #include<iostream> #include<cstring>…

Jennie 区间最长子序列的变体罢了 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; template<cl…

Jisoo 终究还是少想了一步hhh 显然如果a&b为0，那么a去掉任意数量的1（在位上）后&b还是零 所以我就想对于每一个数，枚举和&后可能的值，异或，找找存不存在 然后就挂了 看了题解才知道这种问题可以自上而下地暴力解决。 首先搞一个$inf=(1<<22)-1$，然后这个$(inf $^$ {a_i})$&…