小衣同学的博客

dp[x]表示（x所在连通块里本来没有服务器）如果有装一个服务器的机会，装在x这个连通块里，使得x里的所有上网点，不再需要通过x的父亲fa[x]对应的原图的边进到另一个连通块里时，可以节省的最大权值之和是多少。形如h[i][z]=min(f[u][x]+g[v][y]+F(u,v)，x+y=z)这种式子，但是用树形背包的trick，开大小是连通块大小的vector，复杂度就是O(n^2)的了，计u是左连通块的祖先，v是右连通块的祖先，w是这条边的权值，

f[i][j]=max(k从j到m-1 g[i-1][k]+sum[j,k+1]+max(0,sufmax[k+2:m])) sum[k+1]-sum[j-1] (g2)f[i][j]=max(k从j+1到m f[i-1][k]+sum[j,k]+max(0,sufmax[k+1:m])) sum[k]-sum[j-1] (f1)g[i][j]=max(k从1到j-1 g[i-1][k]+sum[k,j]+max(0,premax[1:k-1])) sum[j]-sum[k-1] (g1)

长为n(n<=2e5)的两个序列a和b，第i个数分别ai(-1e9<=ai<=1e9)，bi(-2e14<=bi<=2e14)倘若k=x最优决策是在大于j的位置取到的，那么一定是将k=x在j处决策后的最优决策调的更优了，把相同的调优手段应用给k=x+1，也能使k=x+1更优，与k=x+1的最优决策在j矛盾。那么当i变为i+1的时候，如果无脑选第i+1个位置，就构成了一种k=x+1的决策。考虑k=x的时候，已经在i处取到了[1,i]的最优决策，此时k=x的最优决策在i+1处取到，否则还是在第i处取到。

假设最后一段x个数，说明冲突了x-1次，容斥系数是(-1)的x-1次方，加上对应的贡献即可。前0个数分成偶数段方案数为1，分成奇数段方案数为0，对应dp[0][0]=1。2. 注意到，第二维对容斥系数的贡献，只有第二维的奇偶性，所以可以改写为。构造一个序列b，要求bi∈[1,ai]，且b[i]不等于b[i+1]其中，dp[i]表示以i结尾的方案数，枚举最后一段合并了几个数，那么，ai对前面的位置的数，也就是k

即dp值来源于两部分，一部分是最终栈中的dp值之和，一部分是本次弹栈的位置的dp值之和。所以可以分成两部分维护，分别维护单调栈自底到顶的dp值之和，和dp值的前缀和。dp[i]表示只考虑[1,i]，i作为最后一个元素必取时，合法的方案数。那么此时单调栈自底到顶还是单增的，栈底的值可以把上面的值再删掉。4. 操作[5,6,8,9]，用5把剩下的删了，7在5后面。3. 操作[8,9,7]，用7把9和8删了，7在6后面。2. 可以操作[9,7]，用7把9删了，7在8后面。从左到右扫完之后，求的是前缀合法的情况，

第一条轴上给定m(m<=1000)个点，第二条轴上给定n(n<=1000)个点，点坐标x(0<=x<=1000)d即线上修建k个点，轴上n+m个点，到线的距离为s/2，每个点到最近点的距离平方的和最小。那么每个修建的点对应的肯定是一段连续的区间，枚举最后一个修建点对应了哪一段朴素dp即可。在距两条轴距离相等且平行的线上，标记k(k<=100)个位置点，使得n+m个点，点i对k个位置中距离最近的点算距离，记为xi。首先，由于轴两侧是等距的，可以把轴上的点合到其中一侧并排序，，将所求式展开，分别为。

假设这中间的线段有k2条，dp[i][j]就可以从dp[x][j-k2]转移而来，用了k2次机会，使得i不被覆盖。dp[i][j]表示当前考虑到点i，已经用了j次撤销机会，点i必不被线段覆盖时，[1,i]的答案最大是多少。m(m<=2e5)天，第i天让区间[li,ri](1<=li<=ri<=n)的城市都下雨，假设位于点x，然后就只需要考虑左端点位于[x+1,i]之间，且右端点在点i及右侧的线段，转化一下题意，即等价于数轴上点[1,n]，m条线段，你可以撤掉最多k条线段，SSRS代码（ST表优化dp）

第i个怪物有stri(1

计点i的点权是ai，最大化(u,v)点对的数量，使得a[u]

可以将X分成若干段，得分为每一段的乘积（可以不分割，此时得分为X）求所有2的n-1次方种分法的得分之和，答案对998244353取模。发现前一部分可以用dp[i-1]表示，于是前缀和优化即可。dp[i]表示到考虑到第i位时的分法之和，枚举最后一段取什么，复杂度是O(n^2)的。给定一个n(n

力扣天池赛-221021天池-04. 意外惊喜(分治优化dp)

Educational Codeforces Round 137 (Rated for Div. 2) F. Intersection and Union（动态dp(线段树+矩阵+dp) /组合数学）

题目T(T<=500)组数据，每次给出一个长为n(2<=n<=3e3)的数组，第i(0<=i<n)个位置是ai，表示i可以跳到[i+1,i+ai]的任意整点位置特别地，如果ai的值是0，就代表在此点不可跳现在要修改一些点的a值，使得从0跳到n-1只有唯一一条路径，求最小修改数保证输入时一定有至少一条路径可达，且sumn<=3e3题解改值显然改成0是最优的，相当于切断了这个点的所有后继，dp[i][j]表示这条路径倒数第一个在i，倒数第二个在

题目n(n<=5e3)块木板，每块木板有两个参数，w(1<=w<=1e7)和h(1<=h<=1e7)，木板不能旋转，两块木板拼接的时候，高度以矮的那块木板为准，把高的那块截掉一部分浪费掉，然后拼接起来，新的木板为w1+w2，高度为min(h1,h2)，问将n块拼接成k块木板所要浪费的最小面积是多少思路来源https://blog.csdn.net/weixin_43823767/article/details/99849399https://ww

题目一个长为n(n<=1e5)的数组a[]，ai<=n，要求把这个数组分成k个连续的段，每一段的代价，是其中相同的值产生的无序对数量之和最小化代价，求这个代价思路来源官方题解https://www.luogu.com.cn/blog/zhongyuwei/solution-cf868f题解先按官方题解，证一下决策点的单调性，即设[1,i]分成k段时，最后一段为[pos,i]，则[1,i+1]分成k段时，最后一段为[pos2,i]，一定满足pos2&