Scorpioch

分类

01分数规划(1) dp(4) gcd(2) NOIP膜你赛(1) OIer的刷题记录(25) poj(3) sgu(1) 【神奇的】模板(1) 二分(1) 动态规划 - 数位DP(1) 动态规划 - 概率DP(1) 动态规划 - 背包(2) 字符串 - KMP(1) 搜索(1) 数学(2) 数据结构 - 线段树(4) 数论(2) 未归档(72) 算法(1) 背包问题(1)

/ 注册

全部文章（共109篇）

【洛谷 P1352】【codevs1380】没有上司的舞会

链接：https://www.luogu.org/problem/show?pid=1352 题意：求n个点的最大带权独立集算法：显然树形DP * 分析：用dp[u][1]表示选第u个人时以u为根的子树的最大欢乐度，dp[u][0]表示不选第u个人时以u为根的子树的最大欢乐度。 * 又上司...

2017-05-11

0 347

【HDU 2438】 Turn the corner

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2438 题意：给出多组x，y，l，d，回答能否通过题解: 图好丑啊啊啊啊啊啊啊啊！！！！！数学题。。。。。难度主要在于列个函数关系式只要保证(PH)max<=y即可然...

数学

2017-05-06

0 438

【模板】【洛谷 P3382】三分

链接：https://www.luogu.org/problem/show?pid=3382 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> usin...

2017-05-06

0 403

【洛谷P1006】传纸条

链接：https://www.luogu.org/problem/show?pid=1006 方格取数的加强版典型多进程动归如果开四维数组，可能会爆空间，所以要优化注意到一个非常优美的性质：如果把两次取数看做同时进行的话，若分别走到（i，j）和（k，l），则有i+j=k+l，也就是说...

2017-05-03

0 427

【洛谷P1004】方格取数

链接：https://www.luogu.org/problem/show?pid=1004 这是一道很经典的多进程动态规划题一个自然的想法是：贪心地将前面的取过的数全赋成0，然后再取一次，然而并不对（QAQ）第一次取的显然是最大值，但第二次取的未必是次大值，所以两条非最大的路，也许比一条...

2017-05-03

0 543

【洛谷P2758】编辑距离

链接：https://www.luogu.org/problem/show?pid=2758 这种题显然DP 令F[i][j]表示a的前i个字符与b的前j个字符的最短编辑距离则分别对应三种操作可以得到动态规划方程 1.a[i]与b[j-1]已编辑完成删除 a[i] 2.a[i-1]与b...

2017-05-02

0 506

【模板】KMP

KMP算法贴个链接：http://blog.csdn.net/v_july_v/article/details/7041827 这个博客讲的蛮不错本人比较懒就不做过多解释了（hhh）只是重申几个比较核心的思想与概念 1.字符串匹配的加速主要在于在匹配过程中失配的情况下，有效地多往后面...

2017-05-02

0 392

【洛谷P1880】合并石子

合并石子 Part 1: 链接：https://www.luogu.org/problem/show?pid=1880#sub 数据范围：1 < N <= 100 题解：朴素算法O(n^3)可过 DP[i][j]表示合并i到j的最小(大)代价每堆石子可以看成先合并成两大堆石...

2017-04-29

0 402

【洛谷P3370】【NOIP2013】火柴排队

链接 https://www.luogu.org/problem/show?pid=1966 题意：两个长度为n的数组a,b ,每次调换一个数组中的两个数，使得∑(a[i]-b[i])^2最小，求最小移动次数题解：可以对所求的式子进行简单的等价变形即∑(a[i]-b[i])^2)=∑a...

2017-04-29

0 351