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篇）

【洛谷P1434】滑雪

题意：找一个二维的最长上升子序列题解： 1.贪心对每个点的高度进行排序，然后再DP，这样就可以保证在转移的时候，上一个状态一定已经被计算出来（好像会wa） #include<cstdio> #include<iostream> #include<algori...

2017-05-29

0 405

【HDU3068】【模板】最长回文

Manacher算法的裸题下面简单说一下复杂度为O（n）的马拉车算法首先过程中涉及到的变量有： p[i]表示以t[i]字符为中心的回文子串的半径 id为最大回文子串中心的位置 mx是回文串能延伸到的最右端的位置通过p数组我们就可以找到最长回文子串及其位置，，那么下面我们就来看如何求...

2017-05-28

0 425

【POJ1986】【模板】LCA

LCA 最近公共祖先倍增法 f[i][j]表示i的2^j祖先，f[i][0]即表示i的父亲首先预处理出f数组，一次dfs然后递推即可接下来求LCA，思路就是让两个需要求LCA的点上升到同一层，然后一直向上找到他们LCA的子节点即可详细说明代码里有 #include<iost...

2017-05-28

0 440

【poj1804】【poj2299】【模板】求逆序对

刚写了一发归并排序的逆序对（不会写二分的蒟蒻）那就顺便复习一下树状数组求逆序对吧来道裸题题目:http://poj.org/problem?id=1804 题意:给定一个序列a[],每次只允许交换相邻两个数,最少要交换多少次才能把它变成非递降序列. 归并排序是将数列a[l,h]分成两...

2017-05-13

0 483

【5.13test】SJR 的金字塔

SJR 的金字塔 (pyramid) 问题描述有一群机房小伙伴潜入SJR 的金字塔盗宝。当他们打开一个宝箱的时候，突然冒出一阵烟（潘多拉的盒子？），他们迅速意识到形势不妙，三十六计走为上计…… 由于他们盗得了金字塔的地图，所以他们希望能找出最佳逃跑路线。地图上标有 N 个室，她现在就在 ...

2017-05-13

0 385

【洛谷P1108】低价购买[LIS方案数]

链接：https://www.luogu.org/problem/show?pid=1108 题意：求最长下降子序列及去重方案数第一问求 LIS 不解释第二问主要难度在于去重可以用 <nobr> g[i] </nobr>表示以第i个数字结尾的LIS...

2017-05-13

0 432

【cogs2230】采药(加强版)

链接：http://218.28.19.228/cogs/problem/problem.php?pid=2230 题解：论一类神兽的毒瘤数据和奇技淫巧题的解题技巧朴素算法O（NM）妥妥要挂但这道题考的是脑筋急转弯…… 注意到v，w的数据范围特别小，也就是说所给出的物品中一定有许多是...

背包问题

2017-05-12

0 580

【NOIP2015】【洛谷2679】子串

链接：https://www.luogu.org/problem/show?pid=2679 题解： 1.求方案数，结合数据范围，可以考虑用DP解 2.令f[i][j][k][0/1]表示A串用了前i个字符，B串已覆盖前j个字符，目前为止已经选了k个子串，最后的0/1表示A串的这个字符选了没有...

2017-05-11

0 340

【poj1456 】supermarket

题目链接：http://poj.org/problem?id=1456 题意：有N件商品，分别给出商品的价值和销售的最后期限，每天仅可售出一件商品，求最大利润。题解：贪心用visit数组标记当天是否有商品售出，将商品的价值从大到小排序，依次取出商品，从它的最后期限向前扫描出没有商品...

poj 贪心算法

2017-05-11

0 428

【HDU3449】 consumer

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3449 题意：有n个箱子，每个箱子有一个价格v，每个箱子中有若干个物品，规定在购买物品前必须购买包含该物品的箱子，问能买到的最大价值题解; 有依赖的背包问题 F[i][j]表示前i个箱子花费j元...

dp

2017-05-11

0 404