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

题意:

求n个串的最长公共子串,n<=10

思路:

不会啊orz

先放一波参考资料&题解好了。

codeforces_Understanding Suffix Automaton in depth

code风景区_spoj_lcs2

code风景区_sam教学

candy SPOJ 1812 LCS2 [后缀自动机 DP]

 

首先参考下2个串的LCS的做法spoj-lcs

 

卧槽终于懂了…

一个串在上面走的时候记录与每个状态公共子串的最大值,注意出现次数向父亲传递,一个状态能到达说明了Suffix Link指向的状态可以取到最大子串,这一步对val后基数排序然后倒着更新就行了

 

…代码之后补

关键是理解这句话:一个状态能到达说明了Suffix Link指向的状态可以取到最大子串

比如如果状态S(从初始状态到S状态所表示的子串是abcbc) 能够最长向前匹配的长度是x,那么状态s的par的状态Q(从初始状态到Q状态所表示的子串是bc)也至少为x.

所以dp[link[v]] = Max{dp[link[v]],dp[v]}

 

妈个鸡。。。

没事改什么字符集大小啊。。。

上道题做的是数字。。就手贱把字符集的大小改成了12.。。忘了改回来。。WA到死。。。

 

 

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

http://poj.org/problem?id=3249

题意:

给一个DAG,现要从一条入度为0的点到一个出度为0的点,问最大点权和。

思路:

其实比较容易想到搜…不过复杂度会炸?

由于到一个点的最大点权和,需要更新完所有到达它的路线之后才能确定。

容易联想到拓扑排序,我们可以在拓扑排序的同时做dp

dp[v] = max(dp[v],dp[u]+a[v]),初始化对于入度为0的点,dp[i] = val[i].

其实拓扑+dp是一种比较一般化的套路…?

因为拓扑保证了更新顺序

 

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

题目链接

题意:给出n,p,q,r,以及n(1E5)个数,所有数的范围都是[-1E9,1E9],现在问pa[i]+qa[j]+r*a[k]的最大值,满足1<=i<=j<=k<=n

思路:傻逼dp…

我。。好菜啊。。。万年dp苦手。

直接转载官方题解了。。。思路的重点是维护了一个最大前缀值。

dp[i][0] stores maximum of value p·ax for x between 1 and i. Similarly dp[i][1] stores the maximum value of p·ax + q·ay such that x ≤ y ≤ i and dp[i][2] stores maximum value of p·ax + q·ay + r·az for x ≤ y ≤ z ≤ i.

To calculate the dp:

dp[i][0] = max(dp[i - 1][0], p·ai)

dp[i][1] = max(dp[i - 1][1], dp[i][0] + q·ai)

dp[i][2] = max(dp[i - 1][2], dp[i][1] + r·ai)

The answer will be stored in dp[n][2]

 

 

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[i].max表示到当前位置的最大乘积。

dp[i].min表示到当前位置的最小乘积。

dp[i].max = max{dp[i-1].max*a[i],dp[i-1].min*a[i],a[i]};

dp[i].min同理

边界dp[i].max = dp[i].min = a[0]

 

 

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 3×3 grid as illustrated below.

The total number of unique paths is 2.

 

题意:从左上到右下的方案数,有些点不能走。

思路:简单dp…1A

 

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.

数字三角形。。。。从坐上到右下问最短路径。。每次只能向下或者向右。。。

wa了一次。。。是因为边界值赋值成了0.。。求最短路径显然因为赋值成inf才对orz..果然傻了。。

简单的dp我们简单的A.

顺便吐槽一下。。(100,100)的答案会溢出int…然而答案就是负的。。。就没人check一下吗,,,

 

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

2748: [HAOI2012]音量调节

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1814  Solved: 1148
[Submit][Status][Discuss]

Description

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量,所以他决定每一首歌之前他都要改变一次音量。在演出开始之前,他已经做好了一个列表,里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量,他可以选择调高也可以调低。
音量用一个整数描述。输入文件中给定整数beginLevel,代表吉他刚开始的音量,以及整数maxLevel,代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数c1,c2,c3…..cn,表示在第i首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌,你的任务是找到这个最大音量是多少。

Input

第一行依次为三个整数:n, beginLevel, maxlevel。
第二行依次为n个整数:c1,c2,c3…..cn。

Output

输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于0或者高于maxLevel,输出-1。

Sample Input

3 5 10
5 3 7

Sample Output

10

HINT

1<=N<=50,1<=Ci<=Maxlevel 1<=maxlevel<=1000

0<=beginlevel<=maxlevel

思路:
一看数据范围…长着一张dp的脸…
dp[i][j]表示经过i次调整后能否达到音量j.
初始化dp[0][beginlevel] = true.
按顺序转移就好了.
复杂度O(n*MAXlevel)

 

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

1207: [HNOI2004]打鼹鼠

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2854  Solved: 1390
[Submit][Status][Discuss]

Description

鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏:在一个n*n的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠,如果i时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的话,那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格,即从坐标为(i,j)的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格,机器人不能走出整个n*n的网格。游戏开始时,你可以自由选定机器人的初始位置。现在你知道在一段时间内,鼹鼠出现的时间和地点,希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

Input

第一行为n(n<=1000), m(m<=10000),其中m表示在这一段时间内出现的鼹鼠的个数,接下来的m行每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻,在第x行第y个网格里出现了一只鼹鼠。Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠,但同一时刻同一地点只可能出现一只鼹鼠。

Output

仅包含一个正整数,表示被打死鼹鼠的最大数目

Sample Input

2 2
1 1 1
2 2 2

Sample Output

1

HINT

Source

 

思路:很巧妙的题目。类比LIS,如果两只仓鼠的曼哈顿距离小于等于两只仓鼠出现的时间,那么就可以从一只仓鼠转移到另一只仓鼠。利用这个条件,做二维的LIS即可。

 

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

题目链接

题意:容量为V的背包,n个骨头,给出价值和体积,问最多能装多少价值的背包。

思路:01背包裸体。

 

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

hdu1864题目链接

题意:中文题目,不多说了。

思路:正解是01背包,呵呵呵。

出题人是傻逼吗?

不给数据范围?

以及,正解的01背包基于所有的发票额度的只有2位小数。这是让人猜?

本来看到这题这么恶心时不打算写的…

写了的原因纯粹是为了吐槽傻逼出题人..

简直是我做得最垃圾的题目之一。

 

 

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

题目链接

题意: 给出n个银行 ,以及抢劫每个银行可以得到的价值和被抓的概率,不同银行之间被抓的概率是相互独立的,现在给出安全概率p,只有当概率从小于安全概率时才是安全的,问最多能抢劫多少价值。

思路:一开始很直接就想到把概率算成容量,

于是就成了经典的01背包,然后发现概率是double型。。。想当然得以为最多是2位小数,于是都*100转化成了整数做01背包。

然而正确思路是,把银行价值看成背包容量,而背包价值是概率!

将危险的概率转化成安全概率(1-危险概率=安全概率)

然后做01背包。

然后从大到小扫一遍价值,第一个大于安全概率的就是答案。

注意精度。

 

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

题目链接

题意:给出n(n<=1E3)个字符,字符可能为’D’,’I’,’?’,第i位对应的字符分别表示,第i位大于第i+1位,第i位小于第i+1位,或者不确定。

现在问满足该字符串的 1..n的排列的方案数。结果%1E9+7

思路:没有太多思路,参考了题解

主要是状态表示没有想到,后面的状态转移方程倒是不难。

思路是,dp[i][j]表示长度为i,最后一位的相对大小为j的方案数。

考虑转移:如果第i-1个位置的字符为‘I’,那么所有比j小的都可以转移到j,也就是dp[i][j] = dp[i-1][1] + dp[i-1][2] + … + dp[i-1][j-2] + dp[i-1][j-1];

如果第i-1个位置的字符是’D’,此时是这道题的重点。

有这个一个有趣的性质,比如对于一个排列{1,3,2},现在我们在递推得到dp[4][2],也就是要把2添加到这个排列的最后面,现在把当前排列即{1,3,2}中大于等于2的全部加上一得到{1,4,3},这样是仍然不会改变题目给出的关系的,然后我们再把2添加到最后,{1,4,3,2},就可以得到dp[4][2]了

此时的复杂度是n3,可以用前缀和优化掉一个n,复杂度n方。

最后答案就是sum[len+1][len+1]

 

 

 

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

题目链接

题意:问长度为n的“波浪”型排列(即1..n每个数出现一次)有多少。波浪型的含义是,“高低高”或者“低高低”

思路:我们考虑当前已经知道i-1个数的波浪型的排列的方案数,那么当第i个数到来时,第i个数一定是最大的。

那么将i插入到某个位置,必须满足该位置前面必须以“高低”结尾,该位置后面必须以“低高”结尾才合法。(特别地,允许前面或者后面为空,这点体现在初始化上)

因此我们分别考虑,用dp[i][0]表示有i位且最后结尾为“高低”的方案数,dp[i][1]表示有i位且最后结尾为“低高”的方案数。

此时我们的情况是,已经有i-1个数,我要把第i个数插在某个位置。

这个位置是不确定的,因为我们需要枚举插入的位置(表现为,枚举插入的第i个数前面有j个数,后面剩余i-1-j个数)

那么第i个数前面是选择哪j个数呢? 组合数为C[i-1][j] (i-1个数选择j个放在前面)

因此长度为i的答案为sum[i] = sigma{dp[j][0]*dp[i-j-1][1]*C[i-1][j]} (0=<j<i)

dp[i][0]和dp[i][1]对称,显然相等,都等于sum[i]/2.

我们只需要再预处理一个组合数就好了。

 

 

 

 

 

【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<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2…Am(0<=Ai<=9)有M位,不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为
0

Input

  第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000

Output

  阿申想知道不出现不吉利数字的号码有多少种,输出模K取余的结果.

Sample Input

4 3 100
111

Sample Output

81

思路:

这次总算想对了状态表示:dp[i][j] 表示当前处理到第i位,最后j位与不吉利串相同的方案数。

然后此时考虑转移,也就是观察第i+1位。

根据第i+1位字符的不同,转移到的 位置也不相同。

从dp[i][j] 可以转移到dp[i+1][k],这种转移表现为dp[i+1][k] += dp[i][j] (k取决于第i+1位字符)

我们可以用f[i+1][k]+=f[i][j]*trans[j][k],trans[j][k]表示串s后j位与不吉利串前j位相同,

添加一个字符后后k位与不吉利串前k位相同的方案数。

%e9%80%89%e5%8c%ba_001

就是说中间的那一部式子可以化简成矩阵的形式。。因此整个递推式就成了矩阵乘法的形式。

tran数组可以用kmp预处理出来。

 

重点是注意体会在字符串上dp的思想。

 

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

题目链接

题意:问长度为n,每个位置由且仅有‘H’和’T’组成的序列中,至少有连续k个‘H’出现的方案数。

思路:不会做,参考了题解 不过没有完全搞懂。

根据题解,正面考虑比较麻烦,所以反面考虑。[j]

dp[i][j]表示长度为i,前面最后连续的‘H’的个数不超过j个的方案数。

考虑转移方程为:

总的情况为:dp[i][j] = dp[i-1][j] * 2;

但是其中有多考虑的情况,就是第i位是’H’,且i位之前的最后j个位置都是’H’(即从i-j位到第i-1位都是‘H’,此时第i-j-1位必然是’T’)

有i个硬币时,如果i < j+1,那么它对于i-1的情况来说,最后一个硬币的位置就可以随便放了。

如果i > j + 1,dp[ i ] [ j ]  = dp [ i – 1 ] [ j ] * 2 – x(不满足条件的部分)

然后我们来考虑这个x怎么求,既然是不满足条件,那么肯定是第i的位置放了H,前面的都是H,从而这些连续的H大于j。那么就考虑dp[ i – 1 – j – 1 ](中间这 j – 1 个(kk:疑似作者笔误。应该位j个)全为H,加上第i个H,就不满足条件了),所以:

dp [ i ] [ j ] = dp [ i – 1 ] [ j ] * 2 – dp [ i – j – 2 ] [ j ](kk:仍然不是很懂这个式子…)

那么我们就差最后一个了:i == j + 1的情况了。(因为 i – j – 2 就等于 -1 了,用递推公式会RE的)

这种情况只有一种,即是全是H。

那么它就为:dp [ i ] [ j ] = dp [ i – 1 ] [ j ] * 2 – 1

 

 

 

最后,要用到高精度,干脆写了java