ComplexPug

未归档

做题记录(1)

/ 注册

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

JXOI2018守卫区间DP

链接 https://loj.ac/problem/2545 思路 f[i][j]表示i到j区间的最小监视人数可以预处理出来g[i][j],表示i能否监视到j (其实预处理的关系不大，完全可以直接判断,不过比较不能加=) 一个区间\([l,r]\)，一定会选r，显然然后只要管r不能监视的地...

DP 区间DP

2019-02-28

0 560

bzoj2091: [Poi2010]The Minima Game DP

2091: [Poi2010]The Minima Game DP 链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2091 思路这类问题好迷呀。我们先从小到大sort 先手一定是个后缀。因为你不能留下大数让对手选呀。然后后手就...

DP

2019-03-29

0 723

bzoj1133: [POI2009]Kon

bzoj1133: [POI2009]Kon 链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1133 思路 f[i][k]表示前i个，选了k个，其中必选i的最大值 f[i][k]=f[j][k-1]+贡献这个贡献就是j到i之间的边界...

DP

2019-03-28

0 552

luoguP1281 书的复制 DP，贪心

luoguP1281 书的复制链接 https://www.luogu.org/problemnew/show/P1281 思路简单dp，输出方案。很明显dp记录路径对不对？恭喜你死了。求出dp值，倒叙贪心取最长错误好久之前咕咕的题目下载数据才看出来不能记录路径代码 ...

DP 贪心

2019-03-29

0 514

luoguP1850 换教室

luoguP1850 换教室链接 https://www.luogu.org/problemnew/show/P1850 思路状态很显然就是f[n][k][0/1] 前i次，用了k次机会,当前是在哪个教室转移就很、、了。每次转移i的时候，一定是从i的两个可能的教室来的。那就有四种可...

DP 期望

2019-03-30

0 523

CF Round #551 (Div. 2) D

CF Round #551 (Div. 2) D 链接 https://codeforces.com/contest/1153/problem/D 思路不考虑赋值和贪心，考虑排名。设\(dp_i\)是子树i中的i是第dp_i大的(相同大小放在后面)。 \(opt=1,dp_u=max(d...

DP

2019-04-19

0 514

bzoj1023: [SHOI2008]cactus仙人掌图

1023: [SHOI2008]cactus仙人掌图链接 bzoj 思路仙人掌求两点间最短路最大。姑且叫他仙人掌的直径。 f[u]表示u为端点的最长的最短路当他是圆圆边，和树上一样dp转移。圆方边，取出环了进行别的dp。转化成带权的环上更新两端距离的最短路的最大值，单调队列。最后...

仙人掌圆方树 DP

2019-05-31

0 574

bzoj4316: 小C的独立集

bzoj4316: 小C的独立集链接 bzoj 思路不是环的边==没有上司的舞会。其他的，把环拿出来,考虑与深度最小的点u的交界处的点选不选，进行两次dp更新f[u] 代码 #include <bits/stdc++.h> using namespace std; co...

圆方树仙人掌 DP

2019-05-31

0 567

# [SDOI2019]移动金币阶梯博弈 dp

[SDOI移动金币链接 vijos 思路阶梯博弈，dp统计. 参见wxyww 代码 #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 7, mod = 1e9 + 9; int read()...

DP 博弈论

2019-06-04

0 682

cf1173 D. Nauuo and Circle

链接 [cf]http://codeforces.com/contest/1175/problem/F) 思路当1在1的位置做dp[i]为i的子树所有的方案。一条性质是i的子树所占圆上的位置一定一段连续的。那\(f[i]\)的方案就是$(son[i]+(i!=1))!\prod\limi...

DP

2019-06-09

0 610