ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共5篇）

luoguP4072 [SDOI2016]征途

[SDOI2016]征途大体大概就是推推公式，发现很***的\(n^3\)DP get60 进一步我们发现状态不能入手，考虑优化转移套个斜率优化板子每一层转移来一次斜率优化思路先便便式子 \[s^2=m^{2}*\frac{\sum_{1}^{m}(a_{i}-\overline...

DP 斜率优化

2019-01-04

0 609

bzoj 3437 小p的农场

bzoj 3437 小p的农场思路 \(f[i]=min(f[j]+\sum\limits_{k=j+1}^{i}{b[k]*(i-k)}+a[i])\) \(f[i]=min(f[j]+\sum\limits_{k=j+1}^{i}{(b[k]*i-b[k]*k)}+a[i])\) 再来前缀...

DP 斜率优化

2019-01-12

0 528

bzoj4709 柠檬单调栈,DP,斜率优化

目录思路错误代码 /* 思路 s是值等于a[i]的前缀和转移方程$f[i]=max(f[i],f[j-1]+a[i]*(s[i]-s[j]+1)*(s[i]-s[j]+1))$ 不难写出暴力方程(by wxyww) //@baol...

单调栈 DP 斜率优化

2019-01-13

0 573

loj2353. 「NOI2007」货币兑换

loj2353. 「NOI2007」货币兑换链接 https://loj.ac/problem/2353 思路题目不重要，重要的是最后一句话提示必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。所以f[i]表示第i天最大收益...

cdq 斜率优化

2019-03-22

0 517

loj#2483. 「CEOI2017」Building Bridges 斜率优化 cdq分治

loj#2483. 「CEOI2017」Building Bridges 链接 https://loj.ac/problem/2483 思路 \[f[i]=f[j]+(h[i]-h[j])^2+(sum[i-1]-sum[j])\] \[f[i]=f[j]+h[i]^2+h[j]^2-2*h...

斜率优化 cdq

2019-03-22

0 506