zcmimi's blog

categories/刷题记录/共659篇文章

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

点击跳转

一定是我做题太少了

看不出这是个最小割

我们将每个人看成一个点,然后如下建边:

  1. 源点向每个人连流量为其总收益的边(\sum_{j=1}^n E_{i,j})

  2. 每个人向汇点连流量为其花费的边

  3. ij连流量为E_{i,j} \times 2的边

然后用所有能赚到的利润减去最小花费就可以了

第三条,如果两个人都选,可以获得E_{i,j}的利润

如果有一个不选,会亏损E_{i,j}的利润

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

点击跳转

f[i][j]表示前i个数选了j个最多多少

f[i][j]=\max(f[i-1][j-1]+[a[i]=j],f[i-1][j]);

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

点击跳转

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

点击跳转

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

点击跳转

可以理解成从左上角到右下角的最长路(每层只能取一个)

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
查看原题

点击跳转

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

点击跳转

f_i为前i个最小代价

s_i为前i个字符串总字符数

f_i=\min(f_j+|(s_i-s_j)+(i-j-1)-L|^p)

可以发现这个方程有决策单调性

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

点击跳转

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

点击跳转

很裸的树形dp

因为是二叉树,所以处理起来非常方便

f[i][j]为根为i的子树用了j条边,最多保留多少,

l,r表示左右节点,lw,rw表示连接左右儿子的边的权值分别为多少

f[i][j]=\max(lw+f[l][j-1],rw+f[r][j-1])

f[i][j]=\max(lw+f[l][k-1],rw+f[r][j-k-1])

40/66
Search
search