DP总结2
上一篇简单的介绍了DP的实质
这一篇介绍DP的应用啥的
1、背包模型
包括0-1背包、无限背包、有限背包、有价值背包、小数背包（贪心即可)等，是极为经典的模型，其转化与优化也是很重要的。
1.01背包
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
方程
i=1..n
j=c[i]..0
f[j]=max(f[j],f[j-c[i]]+w[i])
2.完全背包
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
方程
i=1..n
j=0..c[i]
f[j]=max(f[j],f[j-c[i]]+w[i])
3.多重背包
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
方法
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,…,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出，并不难，希望你自己思考尝试一下。
这样就将第i种物品分成了O(log n[i])种物品，将原问题转化为了复杂度为O(V*∑log n[i])的01背包问题，是很大的改进。
——背包九讲
4.二位费用
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
方程
for (int i=0; i<=V; i++)
for (int j=0; j<=U; j++)
f[i][j]=0; // 边界
for (int i=1; i<=N; i++)
for (int j=V; j>=v[i]; j--)
for (int k=U; k>=u[i]; k--)
f[j][k]=max(s[j][k], f[j-v[i]][k-u[i]]+w[i]);
5.分组背包
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
方程
for 1..k(all groups
for all i blongs to k
for j=V..0
f[j]=max(f[j],f[j-c[i]]+w[i])
6.有依赖的背包
这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。
思路
事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。见下文树形DP
【NOIP2006因为依赖少，可以直接背包
2、最长非降/升子序列模型
设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
O（n2）效率
设长度为N的数组为{a0,a1,a2, … an-1}，则假定以ai结尾的数组序列的最长递减子序列长度为f[i]，则
f[i]={1}
for i=1..n
for j=1..i
if a[j]<a[i]
f[i]=max(f[i],f[j]+1)
ans->max(f[i])
也就是说，我们需要遍历在j之前的所有位置i(从0到j-1)，找出满足条件a[j]<a[i]的f(j)，求出max(f[i],f[j])+1即为f[j]的值。最后，我们遍历所有的f[j]（从0到N-1），找出最大值即为最大递增子序列。时间复杂度为O(N^2)。
O(nlogn)
讲解来自网络
假设存在一个序列d[1..9] = 2 1 5 3 6 4 8 9 7，可以看出来它的LIS长度为5。
下面一步一步试着找出它。
我们定义一个序列B，然后令 i = 1 to 9 逐个考察这个序列。
此外，我们用一个变量Len来记录现在最长算到多少了
首先，把d[1]有序地放到B里，令B[1] = 2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2。这时Len=1
然后，把d[2]有序地放到B里，令B[1] = 1，就是说长度为1的LIS的最小末尾是1，d[1]=2已经没用了，很容易理解吧。这时Len=1
接着，d[3] = 5，d[3]>B[1]，所以令B[1+1]=B[2]=d[3]=5，就是说长度为2的LIS的最小末尾是5，很容易理解吧。这时候B[1..2] = 1, 5，Len＝2
再来，d[4] = 3，它正好加在1,5之间，放在1的位置显然不合适，因为1小于3，长度为1的LIS最小末尾应该是1，这样很容易推知，长度为2的LIS最小末尾是3，于是可以把5淘汰掉，这时候B[1..2] = 1, 3，Len = 2
继续，d[5] = 6，它在3后面，因为B[2] = 3, 而6在3后面，于是很容易可以推知B[3] = 6, 这时B[1..3] = 1, 3, 6，还是很容易理解吧？ Len = 3 了噢。
第6个, d[6] = 4，你看它在3和6之间，于是我们就可以把6替换掉，得到B[3] = 4。B[1..3] = 1, 3, 4， Len继续等于3
第7个, d[7] = 8，它很大，比4大，嗯。于是B[4] = 8。Len变成4了
第8个, d[8] = 9，得到B[5] = 9，嗯。Len继续增大，到5了。
最后一个, d[9] = 7，它在B[3] = 4和B[4] = 8之间，所以我们知道，最新的B[4] =7，B[1..5] = 1, 3, 4, 7, 9，Len = 5。
于是我们知道了LIS的长度为5。
!!!!! 注意。这个1,3,4,7,9不是LIS，它只是存储的对应长度LIS的最小末尾。有了这个末尾，我们就可以一个一个地插入数据。虽然最后一个d[9] = 7更新进去对于这组数据没有什么意义，但是如果后面再出现两个数字 8 和 9，那么就可以把8更新到d[5], 9更新到d[6]，得出LIS的长度为6。
然后应该发现一件事情了：在B中插入数据是有序的，而且是进行替换而不需要挪动——也就是说，我们可以使用二分查找，将每一个数字的插入时间优化到O(logN)~~~~~于是算法的时间复杂度就降低到了O(NlogN)～！
这里上一下代码，因为可以用STL
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 40005
int arr[MAXN],ans[MAXN],len;
int binary_search(int i)
{
int left,right,mid;
left=0,right=len;
while(left<right)
{
mid = left+(right-left)/2;
if(ans[mid]>=arr[i]) right=mid;
else left=mid+1;
}
return left;
}
int main()
{
int T,p,i,j,k;
scanf("%d",&T);
while(T--)
{
scanf("%d",&p);
for(i=1; i<=p; ++i)
scanf("%d",&arr[i]);
ans[1] = arr[1];
len=1;
for(i=2; i<=p; ++i)
{
if(arr[i]>ans[len])
ans[++len]=arr[i];
else
{
int pos=binary_search(i); // 如果用STL： pos=lower_bound(ans,ans+len,arr[i])-ans;
ans[pos] = arr[i];
}
}
printf("%d\n",len);
}
}
例题：合唱队形
3、最大子段和模型
给定长度为n的整数序列，a[1…n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大.或者求出最大的这个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4].
这个题有好几种解法
这里我就讨论两种
1.分治法
求子区间及最大和，从结构上是非常适合分治法的，因为所有子区间[start, end]只可能有以下三种可能性:
- 在[1, n/2]这个区域内
- 在[n/2+1, n]这个区域内
- 起点位于[1,n/2],终点位于[n/2+1,n]内
以上三种情形的最大者，即为所求. 前两种情形符合子问题递归特性，所以递归可以求出. 对于第三种情形，则需要单独处理. 第三种情形必然包括了n/2和n/2+1两个位置，这样就可以利用第二种穷举的思路求出:
- 以n/2为终点，往左移动扩张，求出和最大的一个left_max
- 以n/2+1为起点，往右移动扩张，求出和最大的一个right_max
- left_max+right_max是第三种情况可能的最大值
代码
get_max_interval(array a,left,right)
{
if left==right
return a[left]>0?a[left]:0
mid<-(left+right)/2
max_left_interval=get_max_interval(a,left,mid)
max_right_interval=get_max_interval(a,mid+1,right)
sum<-0
max_left<-0
for i<-mid downto left
{
sum<-sum+a[i]
max_left=max(max_left,sum)
}
sum<-0
max_right<-0
for i<-mid+1 to right
{
sum<-sum+a[i]
max_right=max(max_right,sum)
}
max_mid_interval<-max_right+max_left
return max(max_left_interval,max_right_interval,max_mid_interval)
}
效率O(nlogn)
2.动态规划法
这里主要讨论这个问题的建模过程和子问题结构.时刻记住一个前提，这里是连续的区间
- 令f[i]表示以位置 i 为终点的所有子区间中和最大的一个
- 子问题:如i为终点的最大子区间包含了位置i-1,则以i-1为终点的最大子区间必然包括在其中
- 如果f[i-1] >0, 那么显然f[i] = f[i-1] + a[i]，用之前最大的一个加上a[i]即可，因为a[i]必须包含
- 如果f[i-1]<=0,那么f[i] = a[i] ,因为既然最大，前面的负数必然不能使你更大
对于这种子问题结构和最优化问题的证明，可以参考算法导论上的“剪切法”，即如果不包括子问题的最优解，把你假设的解粘帖上去，会得出子问题的最优化矛盾.证明如下：
- 令a[x,y]表示a[x]+…+a[y] , y>=x
- 假设以j为终点的最大子区间 [s, j] 包含了j-1这个位置，以j-1为终点的最大子区间[ r, j-1]并不包含其中
- 即假设[r,j-1]不是[s,j]的子区间
- 存在s使得a[s, j-1]+a[j]为以j为终点的最大子段和,这里的 r != s
- 由于[r, j -1]是最优解, 所以a[s,j-1]<a[r, j-1],所以a[s,j-1]+a[j]<a[r, j-1]+a[j]
- 与[s,j]为最优解矛盾.
get_max_interval(array a)
{
maxs<-0
f[i]<-{0}
for i<-1 to n
if a[i-1]>0
f[i]=f[i-1]+a[i]
else
f[i]=a[i];
maxs=max(maxs,f[i]);
return maxs
}
效率O(n)
改版：K大子段和、最佳游览，最大子矩阵和等。
最大子矩阵
假如矩阵是一行的，就可以轻松用最大子段和实现
但是，原始矩阵可以是二维的。假设原始矩阵是一个3 * n 的矩阵，那么它的子矩阵可以是 1 * k, 2 * k, 3 * k，（1 <= k <= n）。 如果是1*K，这里有3种情况：子矩阵在第一行，子矩阵在第二行，子矩阵在第三行。如果是 2 * k，这里有两种情况，子矩阵在第一、二行，子矩阵在第二、三行。如果是3 * k，只有一种情况。
为了能够找出最大的子矩阵，我们需要考虑所有的情况。假设这个子矩阵是 2 *k, 也就是说它只有两行，要找出最大子矩阵，我们要从左到右不断的遍历才能找出在这种情况下的最大子矩阵。如果我们把这两行上下相加，情况就和求“最大子段和问题” 又是一样的了。
为了找出在原始矩阵里的最大子矩阵，我们要遍历所有的子矩阵的可能情况，也就是说，我们要考虑这个子矩阵有可能只有1行，2行，。。。到n行。而在每一种情况下，我们都要把它所对应的矩阵部分上下相加才求最大子矩阵（局部）。
比如，假设子矩阵是一个3*k的矩阵，而且，它的一行是原始矩阵的第二行，那么，我们就要在
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
里找最大的子矩阵。
如果把它上下相加，我们就变成了 4, 11, -10,1， 从这个数列里可以看出，在这种情况下，最大子矩阵是一个3*2的矩阵，最大和是15.
为了能够在原始矩阵里很快得到从 i 行到 j 行 的上下值之和，我们这里用到了一个辅助矩阵，它是原始矩阵从上到下加下来的。
就是维护一个矩阵前缀和
int[][] total = matrix;
for (int i = 2; i <=n; i++)
for (int j = 1; j <=m; j++)
total[i][j] += total[i-1][j];
如果我们要求第 i 行到第 j 行之间上下值的和，我们可以通过total[j][k] – total[i-1][k] 得到, k 的范围从1 到 n – 1。
有了这些知识点，我们只需要在所有的情况下，把它们所对应的局部最大子矩阵进行比较，就可以得到全局最大的子矩阵。代码如下：
int subMaxMatrix(int matrix[][])
{
int total[][] = matrix;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= m; j++)
total[i][j] += total[i-1][j];
int maximum = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j <= m; j++) {
//result 保存的是从 i 行 到第 j 行 所对应的矩阵上下值的和
int result[m];
for (int f = 1; f <= n; f++)
if (i == 1)
result[f] = total[j][f];
else
result[f] = total[j][f] - total[i - 1][f];
int maximal = maxSubsequence(result);
if (maximal > maximum)
maximum = maximal;
}
return maximum;
}
4、LCS模型
一个数列 S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。
用烂的图
方程
- 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；
- 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
- 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
代码
#include<stdio.h>
#include<string.h>
#define MAX(a,b) (a>b?a:b)
const int MAXN=1010;
int dp[MAXN][MAXN];
char a[MAXN],b[MAXN];
int main(){
while(~scanf("%s%s",a+1,b+1))
{
memset(dp,0,sizeof(dp));
int i,j;
for( i=1;a[i];i++)
for(j=1;b[j];j++)
if(a[i]==b[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=MAX(dp[i][j-1],dp[i-1][j]);
printf("%d\n",dp[i-1][j-1]);
}
return 0;}
改版：回文字串、多串的LCS等
5、线段覆盖问题
改版：Tom的烦恼（TOJ）等。经常利用到离散化等技巧辅助。
给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。
贪心解法：
首先将线段端点调整为左端点小于（或等于）右端点；
第二，根据右端点将线段从小到大排序；
第三，扫描一遍，每次遇到的第一个与当前的max不相交的即为最优选择。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {
int a,b;
}x[100];
int cmp(node x1, node x2)
{
return x1.b < x2.b;
}
int main()
{
int n;
cin >> n;
for(int i=0; i<n; i++)
{
cin >> x[i].a >> x[i].b;
if(x[i].a>x[i].b) swap(x[i].a, x[i].b);
}
sort(x, x+n, cmp);
int res = 0, max = -1000;
for(int i=0; i<n; i++)
if(x[i].a >= max)
{
res++;
max = x[i].b;
}
cout << res;
return 0;
}
序列型动态规划（DP）：前两步同上，
第三步，dp[i] = max(dp[i], (dp[j]+1))。
第四，选择dp数组中最大值即为结果。
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int n,a[100],b[100],dp[100];
cin >> n;
for(int i=0; i<n; i++)
{
dp[i] = 1;
cin >> a[i] >> b[i];
if(a[i]>b[i])
{
int t = a[i];
a[i] = b[i];
b[i] = t;
}
}
for(int i=n-1; i>0; i--)
for(int j=0; j<i; j++)
if(b[j]>b[j+1])
{
int t = b[j];
b[j] = b[j+1];
b[j+1] = t;
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
int max = 0;
for(int i=1; i<n; i++)
for(int j=0; j<i; j++)
{
if(a[i]>=b[j])
dp[i] = dp[i]>(dp[j]+1)?dp[i]:(dp[j]+1);
if(max < dp[i]) max = dp[i];
//cout << "i:" << i << " j:" << j << " dp[i]:" << dp[i] <<" dp[j]:" << dp[j] << endl;
}
cout << max;
return 0;
}
【来自网络
6、单词划分模型
和LCS基本上构成了字符串DP的主要类型。改版：奇怪的门（TOJ）等。
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
s[i][j]表示从 i 到 j 有多少个单词，f[i][j] 表示将 [0，i] 分成 j 个部分时的最大单词数，则有
for i=0..length
f[i][1]=s[0][i];
for k=2..n
for i=k-1..length
for j=k-2..i-1
f[i][k]=max(f[i][k],f[j][k-1]+s[j+1][i]);
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200;
int n,m,length=0,len[10];
int f[maxn+20][50];
int s[maxn+20][maxn+20];
char a[maxn+20],b[10][maxn+20];
void init()
{
int i,j,k;
scanf("%d%d",&k,&n);
for(i=1;i<=k;i++)
{
scanf("%s",b[0]);
for(j=0;j<20;j++)a[length++]=b[0][j];
}
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%s",b[i]);
len[i]=strlen(b[i]);
}
}
int check(int l,int r)
{
int i,j;
for(i=1;i<=m;i++)
{
if(len[i]>r-l+1)continue;
for(j=0;j<len[i];j++)
if(a[l+j]!=b[i][j])break;
if(j>=len[i])return 1;
}
return 0;
}
void work()
{
int i,j,k;
for(i=0;i<length;i++)
for(j=i;j<length;j++)
for(k=i;k<=j;k++)
s[i][j]+=check(k,j);
for(i=0;i<length;i++)f[i][1]=s[0][i];
for(k=2;k<=n;k++)
for(i=k-1;i<length;i++)
for(j=k-2;j<i;j++)
f[i][k]=max(f[i][k],f[j][k-1]+s[j+1][i]);
printf("%d\n",f[length-1][n]);
}
int main()
{
init();
work();
return 0;
}
THE END