zcmimi's blog

arrow_back动态规划共96篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

考虑排序后的序列

i个人说有a_i个人分数比他高,有b_i个分数比他低

从大到小排序后分数和i相同的人的区间为[a_i+1,n-b_i]

我们设L_i = a_i + 1, R_i = n - b_i

那么如果L_i > R_i显然是假话

如果R_i-L_i+1小于这个区间的人数(L_{i'}=L_iR_{i'}=R_i),那么这也是假话

去掉所有一定是假的话后,问题变成:给若干个区间[l_i,r_i],价值为v_i,从中选出若干个没有交集的区间,价值和最大为多少?

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

区间dp

显然设f[i][j]表示[i,j]最小的表示方法

普通情况:

f[i][j] = \min(f[i][k]+f[k+1][j])

当我们找到循环节:

f[i][j] = \min(f[i][j],f[i][k] + 2 + \text{<循环节个数>})

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f[0] = 0 

i指状态压缩后的二进制数)f[i]=\sum f[i']) 

lowbit可以很快地获取一个数在二进制下第一个1在哪 

一直lowbit和异或就可以把所有1找到 

因为这道题卡常,所以只能用lowbit

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

详见四边形不等式优化

最小值有单调性,可以使用四边形不等式优化

但是最大值没有

但是最大值有个性质:

一定是一直把其他石子合并到某堆石子

那么我们可以f[l][r]=\max(f[l][r-1],f[l+1,r])+S_r-S_{l-1}

相当于一直向左边的石子合并或右边

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

n\le12

f[sta][x]表示状态为sta,当前位置为x的情况下最短的(字典序最小)

f[sta][y]=\min(f[sta'][x]+cost)

看到这个可以联想到AC自动机最短路(貌似是最短哈密顿路径?)

每个字符串长度都小于50,如果用AC自动机可能就核弹打蚊子

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

题意:

给出一个矩阵,要求每行只能选一个节点,每列选的节点不能超过所有选的节点的一半,不能不选, 给出每个节点的选择方案数,求总方案数

解法

考虑到限制是每列选择的不能超过一半,我们可以想到不合法的最多只有一列

我们可以用总方案数减去不符合的

s_i=\sum_{j=1}^m a_{ij}

总方案数:\prod_{i=1}^n (s_i+1) - 1

\because k=\frac {tot}2

所以我们有一个很妙的方法:

设选中目标行之外的权值+1,不选+0,选中目标行权值位+2

最后只要权值> n,那么目标行一定被选了超过\frac n2

f(i,k)表示总共选了i次(也就是选到第i行)权值为k的方案数

f(i,k) += f(i-1,k)*(s_i-a_{ij})(当前行不选目标列

f(i,k+1) += f(i-1,k)(当前行完全不选

f(i,k+2) += f(i-1,k)\times a_{ij}(当前行选中目标列

ans = \prod_{i=1}^n (s_i+1) - 1 - \sum_{i=n+1}^{2n} f(n,i)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

看了看数据范围,可以知道是状态压缩+区间dp

我们设f[i][j][t]表示[i,j]合并后状态为t获得的分数

f[i][j][t] = f[i][k][t'] + f[k+1][j][t''] (t'|t'' = t)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f(i,k)表示将前i个分k次的分数

我们可以dpk次就可以了

f_i为前i个,g_i为上一次dp的结果

f_i=\max_{j=1}^{i-1}(g_j+s_j\times(s_i-s_j))

取任意0\le k<j <i且从j转移比从k更优,那么

g_j+s_j\times(s_i-s_j)\ge g_k+s_k\times(s_i-s_k) 展开得

g_j+s_is_j-{s_j}^2\ge g_k+s_is_k-{s_k}^2 移项得 s_i(s_j-s_k) \ge {s_j}^2-{s_k}^2+g_k-g_j 整理得 s_i\ge \frac{({s_j}^2-g_j)-({s_k}^2-g_k)}{s_j-s_k}

注意s_j-s_k有可能为0,要特判

因为要求的是最大值,所以我们维护一个上凸壳就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

反转子序列相当于多次交换子区间的两端

f[l][r][d][u]为区间[l,r],值域为[d,u]

f[l][r][d][u]=max( \\\\ f[l][r][d+1][u], \\\\ f[l][r][d][u-1], \\\\ f[l+1][r][d][u]+(a[l]==d), \\\\ f[l][r-1][d][u]+(a[r]==u), \\\\ f[l+1][r-1][d][u]+(a[r]==d)+(a[l]==u))(\text{反转})

9/10
Search
search