111qqz的小窝

老年咸鱼冲锋!

SPOJ LCS2 Longest Common Substring 2[后缀自动机+dp]

题意: 求n个串的最长公共子串,n<=10 思路: 不会啊orz 先放一波参考资料&题解好了。 codeforces_Understanding Suffix Automaton in depth code风景区_spoj_lc

poj 3249 Test for Job (拓扑排序+dp)

http://poj.org/problem?id=3249 题意: 给一个DAG,现要从一条入度为0的点到一个出度为0的点,问最大点权和。 思路: 其实比较容易想到搜…不过复杂度会炸? 由于到

codeforces 855 B. Marvolo Gaunt's Ring (前缀最大,dp)

题目链接 题意:给出n,p,q,r,以及n(1E5)个数,所有数的范围都是[-1E9,1E9],现在问p_a[i]+q_a[j]+r*a[k]

leetcode 152. Maximum Product Subarray (最大连续子序列乘积,dp)

Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6. 思路:由于有正,有负,还有0.。。所以比最大子串之和要复杂一些。。。 dp[

leetocde 63. Unique Paths II

Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. [ [0,0,0], [0,1,0], [0,0,0] ] The total number of unique paths is 2. 题意:从

leetcode 64. Minimum Path Sum (二维dp)

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. 数字三角形。。。。从坐上到右下问最短路径。。每次只能向

BZOJ 2748: [HAOI2012]音量调节 (dp)

2748: [HAOI2012]音量调节 Time Limit: 3 Sec Memory Limit: 128 MB Submit: 1814 Solved: 1148 [Submit][Status][Discuss] Description 一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量,所以他决定每一首歌

BZOJ 1207: [HNOI2004]打鼹鼠 (LIS)

1207: [HNOI2004]打鼹鼠 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2854 Solved: 1390 [Submit][Status][Discuss] Description 鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。

(dp专题006)hdu 2602 Bone Collector(01背包)

题目链接 题意:容量为V的背包,n个骨头,给出价值和体积,问最多能装多少价值的背包。 思路:01背包裸体。 /* *********************************************** Author :111qqz Created Time :2016年11月16日 星

[dp专题005]hdu 1864最大报销额(01背包,垃圾题)

hdu1864题目链接 题意:中文题目,不多说了。 思路:正解是01背包,呵呵呵。 出题人是傻逼吗? 不给数据范围? 以及,正解的01背包基于所有的发

(dp专题004)hdu 2955Robberies(01背包变形)

题目链接 题意: 给出n个银行 ,以及抢劫每个银行可以得到的价值和被抓的概率,不同银行之间被抓的概率是相互独立的,现在给出安全概率p,只有当概率从

(dp专题003)hdu 4055 Number String(dp)

题目链接 题意:给出n(n<=1E3)个字符,字符可能为’D’,‘I’,'?',第i位对

【dp专题002】hdu 4489 The King’s Ups and Downs (dp)

题目链接 题意:问长度为n的“波浪”型排列(即1..n每个数出现一次)有多少。波浪型的含义是,“高低高”或者“低高低” 思路:我们考虑当前已经知

【dp专题001】bzoj 1009: [HNOI2008]GT考试 (字符串上dp+kmp+矩阵加速线性递推式)

1009: [HNOI2008]GT考试 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 3127 Solved: 1926 [Submit][Status][Discuss] Description 阿申准备报名参加GT考试,准考证号为N位数X1X2….Xn(0<

[dp专题000]uva 10328 Coin Toss (java 大数+dp)(Unsolved)

题目链接 题意:问长度为n,每个位置由且仅有‘H’和’T'组成的序列中,至少有连续k个‘H’出现的方案数。 思路:不会做,参考了题解

codeforces 605 A. Sorting Railway Cars (dp)

题目链接 题意:给出一个n个数的排列,每次可以把一个数放到最前面或者最后面的位置,问至少要进行多少次操作才能使得数列升序。 思路:考虑不被移动的

hdu 5904 LCIS (dp)

题目链接 题意: 给定两个序列,求它们的最长公共递增子序列的长度, 并且这个子序列的值是连续的 思路:以值为连续做入手点。 很显然个鬼咯 dp[a[i]

斜率优化学习笔记

浅谈数形结合思想在信息学竞赛中的应用 参考博客 这个东西英文好像叫做:convex hull trick Convex_hull_trick_wiki codeforces convex hull trick 简单说说我的理解:斜率优化是一种数形结合的思想。

hdu 5763 || 2016 multi #4 1001 Another Meaning (kmp+dp)

hdu 5763 题目链接 题意:给定两个字符串A和B,每个出现在A中的B(可以overlap)都有两种含义,问A串一共可能有多少种含义。 思路:kmp+dp

codeforces 429 B. Working out (dp)

cf429 b 题目链接 题意: n*m个格子,每个格子有一个人value a[i][j]>0,连个人,一个从左上角到右下角,每次只能向下或者向右移动,