题目大意： 题目链接：http://www.rqnoj.cn/problem/270 给出 n n n个数，求取出几个数使得它们的和为 m m m的方案数。 思路: 很明显是01背包的变形。设 f [ i ] f[i] f[i]表示和为 i i i时的最大答案，那么就有状态转移方程： f [ i ] + = f [ i − a [ j ] ] ( i > = a [ j ] ) f

0 1背包问题的拓展。 注意有一个封顶值为100； 在判断边界条件时，0可取，100不可取。 #include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>using namespace std;#define maxn 110#define INF 9999999int dp[110];i

记忆化搜索很简单，就是用的时候老是想不到~~无奈的感觉~~~ dp[l][r] :l到r这一段中的最小表示方法。 #include<stdio.h>#include<iostream>#include<string.h>#include<algorithm>#include<queue>#include<stack>#include<map>#include<string>

dp[i][j]: 从0到i匹马，住进j个马棚里，最小的不愉快系数。 num[i][j]: 把第i匹马到第j匹马放进一个马棚里，产生的不愉快系数 dp[i][j]=min(dp[i][j],dp[ii][j-1]+num[ii+1][i]); 时间复杂度：n*n*k #include<stdio.h>#include<string.h>#include<algori

就是从后往前搜，一个前指针st，一个后指针ed； 如果后指针ed往后走的过程中出现了可以吃的面包序列。 那么就把st指针尽量的往后走。 这过程中出现的最优值即是答案。 #include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<math.h>using namespace s

逆向思维。 题目要求拿走k本书，那么就求从中拿n-k本书。 dp[i][j]:代表拿第i本书，从前i中拿k本书，最小的整齐度。 num[i]： 第i本书的高度。 dp[i][j]=dp[0...i-1][j-1]+|num[i]-num[j]|; #include<stdio.h>#include<string.h>#include<algorithm>#include<ios

最长上升子序列的O（n*log（n））算法。 不上升子序列的个数等于最长上升子序列的长度。 #include<string.h>#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;#define INF 9999999int dp[10001];int num[10001];in

这道题目是把一个连续的串看成一个环。 那么除了原始的求最大字段和外。 还存在一种情况是前面的连续最大值，加上后面的连续最大值。 #include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>using namespace std;int a[2000002];int st[1000010]

一个二维背包问题。 注意两种物品可以带超过当前值。 那么就算出超过的部分的最小值。 若当前已经超过，那么最小值不可能出现在超过后在加一个值，所以当数值已经超过的时候，就不需要算超过的部分的超过了。 #include<string.h>#include<stdio.h>#include<iostream>#include<algorithm>#include<math.h