expect2004

分类

Codeforces Round(2) Contests(11) review(2) 其他(1) 动态规划(19) 动态规划 - 区间DP(3) 动态规划 - 期望与概率DP(1) 动态规划 - 树形DP(4) 动态规划 - 状压DP(1) 动态规划 - 线性DP(1) 动态规划 - 背包(2) 图论 - Tarjan(4) 图论 - 二分图判定(2) 图论 - 拓扑排序(1) 图论 - 最短路(1) 图论 - 生成树(3) 字符串 - AC自动机(2) 字符串 - KMP(2) 字符串 - 后缀数组（SA）(3) 字符串 - 字典树（Trie）(1) 数学 - 其他(2) 数学 - 多项式(3) 数学 - 组合计数(1) 数学 - 莫比乌斯反演(2) 数学 - 高斯消元(2) 数据结构 - 分块(1) 数据结构 - 平衡树(1) 数据结构 - 树状数组(1) 数据结构 - 树链剖分(2) 数据结构 - 珂朵莉树(2) 数据结构 - 线段树(6) 数据结构 - 虚树(1) 未归档(6) 模板(5) 游记(3) 算法 - 2-SAT(2) 算法 - CDQ分治(1) 算法 - 搜索(2) 算法 - 树分治(2) 算法 - 矩阵树定理(1) 网络流(7) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 网络流 - 最小割(6) 题解(22)

/ 注册

全部文章（共149篇）

LG5200 「USACO2019JAN」Sleepy Cow Sorting 树状数组

\(\mathrm{Sleepy Cow Sorting}\) 问题描述 LG5200 题解树状数组。设\(c[i]\)代表\([1,i]\)中归位数。显然最终的目的是将整个序列排序为一个上升序列，于是倒序枚举，先把最后有序的插入。剩下来前面无序的就是要操作的，于是直接输出操作...

2019-09-22

0 378

LG5196 「USACO2019JAN」Cow Poetry 背包+乘法原理

\(\mathrm{Cow Poetry}\) 问题描述 LG5196 题解因为每句诗的长度一定是\(k\)，所以自然而然想到背包。设\(opt[i][j]\)代表到第\(i\)位时，结尾为\(j\)的方案数。背包，注意\(\mathrm{DP}\)顺序为先枚举\(i\)，后枚举单...

2019-09-22

0 587

20190922 「HZOJ NOIP2019 Round #7」20190922模拟

综述这次是USACO2019JAN Gold的题目。 \(\mathrm{Cow Poetry}\) 题解因为每句诗的长度一定是\(k\)，所以自然而然想到背包。设\(opt[i][j]\)代表到第\(i\)位时，结尾为\(j\)的方案数。背包，注意\(\mathrm{DP}...

2019-09-22

0 375

LG2530 「SHOI2001」化工厂装箱员高维DP+记忆化搜索

问题描述 LG2530 题解设\(opt[i][a][b][c][d]\)代表装到第\(i\)个后，第\(1,2,3\)手上分别还剩\(a,b,c\)个的最小操作数。记忆化搜索即可。启示：如果状态没想法，可以先写爆搜，确定状态。 \(\mathrm{Code}\) #in...

2019-09-21

0 338

LG2893/POJ3666 「USACO2008FEB」Making the Grade 线性DP+决策集优化

问题描述 LG2893 POJ3666 题解对于\(A\)中的每一个元素，都将存在于\(B\)中。对\(A\)离散化。设\(opt_{i,j}\)代表\([1,i]\)，结尾为\(j\)的最小代价。 \[opt_{i,j}=min_{k \in [1,m]} {opt_{i-...

2019-09-21

0 372

TYVJ1071 LCIS 线性DP+决策集优化

问题描述 TYVJ1071 题解暴力\(\mathrm{DP}\) 首先，一个\(O(n^3)\)的解法：设\(opt_{i,j}\)代表\(a\)的前\(i\)个和\(b\)的前\(j\)个的\(\mathrm{LCIS}\). 显然有： 1.\(a_i=b_j\) \[o...

2019-09-21

0 540

LG3004 「USACO2010DEC」Treasure Chest 区间DP+滚动数组优化

问题描述 LG3004 题解把拿走的过程反向，看做添加的过程，于是很显然的区间DP模型。设\(opt_{i,j}\)代表区间\([i,j]\)中Bessie可以获得的最大值，显然有 \[opt_{l,r}=sum_{l,r}-min(opt_{l+1,r},opt_{l,r+1})...

2019-09-20

0 477

LG2770/LOJ6122 航空路线问题费用流网络流24题

问题描述 LG2770 LOG6122 题解教训：关掉流同步之后就不要用其他输入输出方式了。拆点。两个拆点之间连\((1,1)\)，其他连\((1,0)\) \(\mathrm{Code}\) #include<bits/stdc++.h> using na...

2019-09-20

0 417

LG2512/BZOJ1045 「HAOI2008」糖果传递中位数

问题描述 LG2512 BZOJ1045 题解这是一个链状问题的环状版本。问题最终变为给定数轴上的\(n\)个点，找出一个到他们的距离之和尽量小的点，而这个点就是这些数中的中位数。网络流24题的负载平衡问题是双倍经验 \(\mathrm{Code}\) #include...

2019-09-19

0 391

LG2053/BZOJ1070 「SCOI2007」修车费用流

问题描述 LG2053 BZOJ1070 题解将\(m\)个修理工拆为\(n \times m\)个，将修理工和车辆看做二分图，连出一个完全二分图。边流量为\(1\)，费用为时间，费用流即可。 \(\mathrm{Code}\) #include<bits/stdc+...

2019-09-19

0 423