题意：

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

思路：

不会啊orz

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

codeforces_Understanding Suffix Automaton in depth

code风景区_spoj_lcs2

code风景区_sam教学

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

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

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

题意：

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

思路：

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

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

题目链接

题意：给出n,p,q,r,以及n（1E5）个数，所有数的范围都是[-1E9,1E9],现在问p_a[i]+q_a[j]+r*a[k]的最大值，满足1<=i<=j<=k<=n

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

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], …

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.

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

2748: [HAOI2012]音量调节

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

Description

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

1207: [HNOI2004]打鼹鼠

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

Description

鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏：在一个nn的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格 …

题目链接

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

思路：01背包裸体。

/* ***********************************************
Author :111qqz
Created Time :2016年11月16日 星期三 15时14分36秒
File Name :code/hdu/2602.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include …

hdu1864题目链接

题意：中文题目，不多说了。

思路：正解是01背包，呵呵呵。

出题人是傻逼吗？

不给数据范围？

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