zcmimi's blog

arrow_back前缀和共23篇文章

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

点击跳转

记录up[i][j]表示位置(i,j)可以向上多少个#

s[i][j]表示位置(i,j)作为三角形中心可以向左多少个#

S[i][j]表示位置(i,j)作为三角形中心可以向右多少个#

ans = \sum_{i=1}^n\sum_{j=1}^n \min(s[i][j],S[i][j])

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

点击跳转

区间[i,j]如果满足要求,则S_{j-1}-S_i = 0ch[i] = ch[j]

那么先记录前缀和,然后倒着枚举,统计[i+1,n]有多少个满足要求的位置

记得开long\ long

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,要特判

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

3/3
Search
search