# 思路：

codeforces_Understanding Suffix Automaton in depth

code风景区_spoj_lcs2

code风景区_sam教学

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

…代码之后补

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

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

# 思路：

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

## codeforces 855 B. Marvolo Gaunt’s Ring (前缀最大，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.

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同理

## leetocde 63. Unique Paths II

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.

## 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..果然傻了。。

## 2748: [HAOI2012]音量调节

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

3 5 10
5 3 7

10

## HINT

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

0<=beginlevel<=maxlevel

dp[i][j]表示经过i次调整后能否达到音量j.

## 1207: [HNOI2004]打鼹鼠

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

2 2
1 1 1
2 2 2

1

hdu1864题目链接

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

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

## 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),他不希望准考证号上出现不吉利的数字。

0

## Input

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

## Output

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

4 3 100
111

81

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

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

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