DP
DP
1.背包
1. 01背包
这个山洞里有一些不同的草药，采每一株都需要一些时间，一株只能拿一次,每一株也有它自身的价值。在一段时间里，你可以采到一些草药。你应该可以让采到的草药的总价值最大。采药
特点:一个东西拿一次
dp方程:dp[i][j]表示考虑到前i个物品,占了j的体积所拿到的最大的价值,则
if(j>=v[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
else dp[i][j]=dp[i-1][j];如果可以拿,要么拿要么不拿. 如果不能拿那就不拿
ps:优化空间:发现dp[i][j]只与dp[i-1]有关 所以将方程变为dp[j].dp[j]=max(dp[j],dp[j-v[i]]+w[i])
for(int i=1;i<=n;++i)
for(int j=m;j>=v[i];--j)//要倒着来
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);2. 完全背包
这个山洞里有一些不同的草药，采每一株都需要一些时间，一株可以拿无数次,每一株也有它自身的价值。在一段时间里，你可以采到一些草药。你应该可以让采到的草药的总价值最大。疯狂的采药
特点:一个东西拿无数次
dp方程:dp[i][j]表示考虑到前i个物品,占了j的体积所拿到的最大的价值,则
for(int i=1;i<=n;++i)
for(int j=v[i];j<=m;++j)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
3. 分组背包
他的物品大致可分为 k 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
特点:组内冲突
方法:先枚举组再枚举体积最后枚举每组里的每个东西
for(int i=1;i<=n;++i)
{
cin>>v[i]>>w[i]>>c[i];maxx=max(maxx,c[i]);
k[c[i]][++tot[c[i]]]=i;
}
for(int kk=1;kk<=maxx;++kk)
for(int j=0;j<=m;++j)
{
dp[kk][j]=dp[kk-1][j];
for(int i=1;i<=tot[kk];++i)
{
int id=k[kk][i];
if(j>=v[id])dp[kk][j]=max(dp[kk][j],dp[kk-1][j-v[id]]+w[id]);
}
}
cout<<dp[maxx][m];4. 多重背包
特点:每个东西可以选k[i]次
dp[i][j]=dp[i-1][j];
for(int k=1;k*v[i]<=j;++k)//朴素暴力
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);优化:二进制拆分
将k个这个东西分为2^0个,2^1个...2^k个,使这几个刚好可以组成k个东西,然后01背包
5. 附件背包
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明的预算方案
01背包的决策:
1.不选，然后去考虑下一个
2.选，背包容量减掉那个重量，总值加上那个价值。
这个题的决策是五个，分别是：
1.不选，然后去考虑下一个
2.选且只选这个主件
3.选这个主件，并且选附件1
4.选这个主件，并且选附件2
5.选这个主件，并且选附件1和附件2.
6. 混合背包
特点:又有01又有完全又有多重
for(int i=1;i<=n;++i)//简单粗暴
{
if(是01背包)for(int j=m;j>=v[i];j--)dp...
if(是完全背包)for(int j=v[i];j<=m;++j)dp...
}7. 2维背包
特点:有两个费用
for(int i=1;i<=n;++i)
for(int j=0;j<=m1;++j)//费用1
for(int jj=0;jj<=m2;++jj)//费用2
dp[i][j][jj]=max(dp[i-1][j][jj],dp[i-1][j-v1[i]][jj-v2[i]]+w[i]);2.线性DP
1.LIS 最长上升子序列
for(int i=1;i<=n;++i)//dp[i] 考虑前i个,第i个必选的LIS的长度
{
dp[i]=1;
for(int j=1;j<i;++j)
if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);
}O(n^2)
for(int i=1;i<=n;++i)//dp[i]:该序列中，上升子序列长度为i的上升子序列，的最小末尾数值
{
int now=0;
for(int step=(1<<20);step>=1;step/=2)
{
if(now+step<=n&&dp[now+step]<tong[i]&&dp[now+step]!=dp[0])
now+=step;
}
dp[now+1]=a[i];
}O(nlogn)
2.LCS 最长公共子序列
dp[0][0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}3.区间DP
eg:区间合并求分数石子合并
for(int len=1;len<=n*2;++len)
{
for(int l=1;l+len<=n*2;++l)
{
int r=l+len;
for(int k=l;k<r;++k)
{
dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
dpp[l][r]=min(dpp[l][r],dpp[l][k]+dpp[k+1][r]+sum[r]-sum[l-1]);
}
}
}套路:
for(int len=1;len<=n*2;++len)
{
for(int l=1;l+len<=n*2;++l)
{
int r=l+len;
for(int k=l;k<r;++k)
{
dp...
}
}
}