Scorpioch

OIer的刷题记录

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

/ 注册

全部文章 / OIer的刷题记录（共25篇）

【洛谷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

【洛谷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