最大公共子串

解法：动规

考点：最长公共子序列、最大连续和

设两个字符串分别为x和y

f[i][j]表示公共子串以x的第i个字符作为结尾，同时以y的第j个字符作为结尾，能够得到的最大权值。

也就是说，x的第i个字符与y的第j个字符相同，才能得到一个公共子串。于是有：

f[i][j]= max{f[i-1][j-1]+value(x[i]) , value(x[i])}  条件x[i]==y[i]

f[i][j]= -inf                              条件x[i]!=y[i]

时间复杂的O(n^2)  

导航

考点 最短路 最短路上的边

     注意，根据题意和样例，本题是实时更新的最短路，也就是走到了i号点，GPS会立即算出i号点到终点的最短路。

三次SPFA

步骤一：我们要找出哪些边位于1号GPS的最短路上，哪些边位于2号GPS的最短路上

解决过程：

   1.根据1号GPS的地图信息建立反图，终点到每个点的最短距离dis1[i]，然后找出哪些边位于1号GPS的最短路上。

   对于边<x,y>,若dis1[x]-dis1[y]=Length[x][y],那么边<x,y>就在1号的最短路上，否则不在

   2.同理，根据2号GPS的地图信息反图，终点到每个点的最短距离dis2[i]，然后找出哪些边位于2号GPS的最短路上。

   对于边<x,y>,若dis2[x]-dis2[y]=Length[x][y],那么边<x,y>就在2号的最短路上，否则不在

步骤二：统计出每条边的抱怨次数，重新构图

   我们把GPS抱怨的次数当做边的长度。初始时将原图中每条边的长度Len[]设为0.

   枚举原图中的每条边，对于第i条边，若该边不在1号GPS的最短路上，它的长度Len[i]++,

若i号边不在2号GPS的最短路上，它的长度Len[i]++。

   也就是说，如果边i同时位于两个GPS的最短路上，则Len[i]==0。如果只位于1个GPS的最短路上，Len[i]=1。否则Len[i]=2。

步骤三：计算抱怨次数最少的路径

在步骤二建立的图上，从起点到终点跑一次最短路，路径的长度便是最少的抱怨次数。

浇花

考点 区间动态规划

类似于括号dp的讨论方式，讨论i的左边，选哪个数字作为区间的起点，更新i的值

dp[i][k]表示从左往右讨论到第i个数字，i的左边有k个数字还未被用过(被当做区间的左起点), 的方案数。

分两种情况讨论：

情况1：i被别人更新(因为i前面的k个数，任选一个为区间起点，都可更新到i)：

  若a[i]+k==h 则dp[i][k]=dp[i+1][k-1]*k+dp[i+1][k]

  说明，条件a[i]+k==h,因为i左边有k个数字还没用过，那么以这k个数字作为区间左起点可以操作k次，每次都可以更新到i，更新k次，恰好就能使a[i]变成h。

  现在对于i而言，有两种选择， 使用i或者不使用i。

  若用i作为区间右端点，因为i只能当一次区间终点，所以只能从前k个中选一个来与它配对，故有k种方案，k个数中i选了一个，对于i+1它左边就只有k-1个未使用的数了，数量总数为k*dp[i+1][k-1] 。

  注意，这里i不能再作为区间的左端点了，这样的话会导致i被多更新一次，高度变成h+1

  若不用i作为区间端点，则方案数为dp[i+1][k]

情况2：i作为区间起点去更新别人 

  若a[i]+k+1=h则dp[i][k]=dp[i+1][k]*(k+1)+dp[i+1][k+1]

  说明，因为i前面有k个数未被当做左起点使用，全部操作都只能把a[i]更新到h-1这个高度，那么i号点必须自己作为某区间的左起点更新一次，在更新这个区间的同时把自己的高度也更新1，达到h。

  这样，对于下一个数i+1而言，算上i号点，它左侧有k+1个点可选做区间左端点，任选一个选后剩下k个点，状态dp[i+1][k]

  若不用i作为区间左端点，则方案数为dp[i+1][k+1]

时间复杂度O(n2),实现时采用记忆化搜索比较方便。