OceanEye's Blog

是时候表演真正的技术了!

@OceanEye3月前

07/13
14:46
OI

BZOJ4361

神奇树状数组优化DP+组合数
思路很暴力……但是就是比较难连起来

第一步:
dp[i][j]表示枚举到第i位结尾且以第i位为结尾时 不下降子序列长度为j的情况数量

\( dp[i][j]=\sum_{k=1}^{j}(dp[i-1][k]) \)

第二步:
令 g[x] 表示所有长度为x的 不下降子序列 的数量

\( g[x]=\sum_{k=1}^{n}dp[k][x] \)

可以发现我们的ans和这个g[x]是由联系的
长度为x的 不下降子序列 的数量……和两个东西有关系

第一类—->从g[x+1]直接减少一位过来 第二类—->从非g[x+1]的过来 【参照定义理解】
第二类的数量是要记入答案的数量的
就稍微的暴力用n阶乘来做就好了,反正n不大

\( ans=\sum_{k=1}^{n}g[k]*(n-k)!-g[k+1]*g[k+1]*(n-k-1)!*(k+1) \)

以下代码

 

BZOJ4361

@OceanEye5月前

05/29
21:46
OI

BZOJ1079

dp[a][b][c][d][e][pre] = dp[a-1][b][c][d][e][1]*系数 + … + dp[a][b][c][d][e-1][5]*系数

其中a, b, c, d, e是能涂一块砖的颜色数,二,三……五

pre是上一次用的颜色是能涂pre块砖头的

因为上一次用的是能涂pre块砖头的,所以这一次涂色里能涂pre-1块砖头的颜色里有一种颜色不能用了

对应的系数就要-1

code

BZOJ1079

@OceanEye6月前

05/4
19:49
OI

BZOJ4318

期望DP
题目要求维护三次方
所以要把二次和一次的期望也给维护了,接着考虑我们DP的含义是什么。
DP[3][i]=DP[3][i-1] + (增长幅度=x^3-(x-1)^3)*(增长概率=p[i])
上面那个三次方展开一下就可以做了

BZOJ4318

@OceanEye6月前

05/3
18:56
OI

BZOJ1419

期望DP
和班上的一个物理大佬一起搞了二十分钟吧……然后发现这个期望(R,B)只和(R-1,B)以及(R,B-1)相关
然后就一个for循环再用一下滚动数组就可以了
dp[r][b]=(dp[r][b-1]-1)*b/(r+b) + (dp[r-1][b]+1)*r/(r+b)

BZOJ1419