题目要求的是求的最短路， 则对于 不等式  f(b)-f(a)>=c,建立 一条 a 到 b 的边 权值为 c(因为当前点b由源点a与值c来判断),则求的最长路 即为 最小值(集合) 并且有隐含条件：0<=f(a)-f(a-1)<=1  则有边权关系(a,a-1,0)以及(a-1,a,-1); 将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足 它们与该点之间相互差值最

题目链接：POJ 1384 Piggy-Bank Piggy-Bank Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 7880 Accepted: 3801 Description Before ACM can do anything, a budget must be prepared and the

1376：最近零子序列 http://ac.jobdu.com/problem.php?pid=1376 题意 给定一个整数序列，求其最接近0的连续子串和。 思路 DP类题目，注意考虑正数负数两种情况，略复杂一些。 代码 #include <stdio.h>#include <stdlib.h>#include <math.h>#define N 100000struct s

题意 给出一个字符串S（可能有重复的字符），按照字典序从小到大，输出S包括的字符组成的所有排列。例如：S = “1312”，  输出为：  1123  1132  1213  1231  1312  1321  2113  2131  2311  3112  3121  3211 思路 sort函数先将字符串排序，然后通过next_permutation函数对字符串进行排列。

本小结介绍0-1背包、完全背包以及多重背包问题 记忆要点： 0-1背包：二维数组情况下，顺序遍历体积或者倒序均可以                降维情况下需倒序遍历体积 完全背包：数组降维+顺序遍历 多重背包：进行类似于二进制分解的操作，然后转化为0-1背包求解 背包问题变种一： 恰好装满指定的体积 解决思路为初始化时先将dp[ j ]初始化为不存在，而dp[0]初始化为0，遍历过程中先判断前提