题意： 求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后基数排序然后倒着更新就行了 ...代码之后补 关键是理解这句 …

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是一种比较一般化的套路...？ 因为拓扑保证了更新顺序 /* *********************************************** Author :111qqz …

题目链接 题意：给出n,p,q,r,以及n（1E5）个数，所有数的范围都是[-1E9,1E9],现在问p_a[i]+q_a[j]+r*a[k]的最大值，满足1<=i<=j<=k<=n 思路：傻逼dp... 我。。好菜啊。。。万年dp苦手。 直接转载官方题解了。。。思路的重点是维护了一个最大前缀值。 _dp_[_i_][0] stores maximum of value _p_·_a__x_ for _x_ between 1 and _i_. Similarly _dp_[_i_][1] stores the maximum value of _p_·_a__x_ + _q_·_a__y_ such …

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 = …

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

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. 顺便吐 …

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 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> …

hdu1864题目链接 题意：中文题目，不多说了。 思路：正解是01背包，呵呵呵。 出题人是傻逼吗？ 不给数据范围？ 以及，正解的01背包基于所有的发票额度的只有2位小数。这是让人猜？ 本来看到这题这么恶心时不打算写的... 写了的原因纯粹是为了吐槽傻逼出题人.. 简直是我做得最垃圾的题目之一。 /* *********************************************** Author :111qqz Created Time :2016年11月16日 星期三 14时13分28秒 File Name :code/hdu/1864.cpp …