ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共41篇）

hdu 3698 UVA1490 Let the light guide us 线段树优化DP

题目链接 and 题目大意 hdu3698 但是 hdu的数据比较弱，所以在这luogu提交吧UVA1490 Let the light guide us 有一个\(n*m\)的平原，要求每行选一个点，选\(n\)个点建造塔楼。平原上每个点都有他自己的花费时间和魔法值。为了正确控制塔楼，我们...

线段树 DP

2018-10-12

1 504

bzoj1055 ||P4290 [HAOI2008]玩具取名

目录链接思路代码链接 luogu bzoj 思路区间dp 然后\(f[i][j][k]\) 区间\([i,j]\)能否变成\(k\)字符（字符当然得转化一下）字符的个数不多，直接暴力\(check\)，暴力转移就行，\(%...

DP

2018-10-15

1 496

bzoj 3791 作业

思路重要信息是区间m次修改最多能产生2*m-1个区间然后就成了简单dp了代码 //f[j][i][0/1]表示到j这个点分了i段，这一段染色的是0/1的作业数 #include <bits/stdc++.h> using namespace std; #define ll ...

DP

2018-10-16

0 426

hdu4719 Oh My Holy FFF 线段树优化dp

思路好久之前的了，忘记什么题目了可以到我这里做luogu 反正就是hdu数据太水，导致自己造的数据都过不去，而hdu却A了好像是维护了最大值和次大值，然后出错的几率就小了很多也许是自己写错了，忘记了留坑待补代码 #include <iostream> #include &...

DP 线段树

2018-10-31

0 438

P4303 [AHOI2006]基因匹配未完成

题目 luogu 暴力60pts部分显然如果没有出现次数==5的条件显然是\(N_{2}\)的求lcs的模板但是加点条件就完全不同了思路这个题短小精悍，不想数据结构那么***无脑我们考虑一下\(N_{2}\)的缺点首先我们知道，只有a[i]==b[j]的时候才会对答案有所贡...

DP 树状数组

2018-10-31

0 527

P2761 软件补丁问题

P2761 软件补丁问题思路貌似不用网络流，直接状态压缩用spfa跑最短路，直接判断是否能过位运算太渣了，WA了好几发代码 #include <bits/stdc++.h> using namespace std; const int N = 21, M = 101, ...

DP 状态压缩

2018-12-28

0 415

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

[Sdoi2017]序列计数矩阵优化dp

题目 https://www.lydsy.com/JudgeOnline/problem.php?id=4818 思路先考虑没有质数限制 dp是在同余系下的，所以\(f[i][j]\)表示前i个点，和为j的方案数转移就是\(f[i][j]=f[i-1][k]+g[(j-k)\%p]\) g...

DP 矩阵快速幂

2019-02-16

0 519