//3382 整数拆分
将 1,2,4,8看成一个一个的物品，以完全背包的形式放入。
一维形式：f]0]=1;
#include<bits/stdc++.h>
using namespace std;
//3382整数拆分
const int N=1e6+10, M=5e5+10;
int mod=1e9;
int f[N],n;
int main()
{
cin>>n;
//转化为完全背包问题,
//状态是找前i个二进制数，组成j的数量
f[0]=1;
for(int i=1;i<=n;i*=2)//
//和完全背包一样遍历所有物品（以前i件物品）
{
for(int j=i;j<=n;j++)
{
f[j]=(f[j]+f[j-i])%mod;
}
}
cout<<f[n]<<endl;
}
由于二维形式会爆。下面给出写法
需要注意的一点是：由于每次只用到前一层循环的数据，当前层j放不下i的位置，也就是j<i的位置，也要更新，因为下一层可能用到这个数据，不更新的话，就都是0了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10, M=5e2+10;
int mod=1e9;
int f[N][N], n;
int main()
{
cin >> n;
for(int i=0; i<=n; i++)
{
f[i][0] = 1;
}
int t;
for(int i=1; i<=n; i*=2)
{
t=i;
for(int j=1; j<=n; j++)
{
f[i][j] = f[i/2][j];
if(j >= i)
{
f[i][j] = (f[i][j] + f[i][j-i]) % mod;
}
}
}
cout << f[t][n] << endl;
}
2 01 背包问题
注意存w和v的的值是从1开始。因为还要考虑状态i-1
#include<bits/stdc++.h>
using namespace std;
// 2 01 背包问题
const int N=1010;
int w[N],v[N];
int f[N][N];//前N件物品，背包容量
int main()
{
int n,V;
cin>>n>>V;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
//for(int i=0;i<=V;i++)f[0][i]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=V;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][V]<<endl;
}
8完全背包问题
#include<bits/stdc++.h>
using namespace std;
// 8 完全背包问题
const int N=1010;
int f[N][N];
int n,m;
int w[N],v[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
}
9分组背包问题
完全背包问题是k的个数作为循环。分组背包是组内的所有物品作为循环；
#include<bits/stdc++.h>
using namespace std;
//9 分组背包问题
const int N=110;
int f[N][N];
int n,m;
int w[N][N],v[N][N],s[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int t;
cin>>t;
s[i]=t;
for(int j=1;j<=t;j++)
{
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
for(int k=1;k<=s[i];k++)
{
if(v[i][k]<=j)
{
f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
}
cout<<f[n][m]<<endl;
}
//6 多重背包问题III
多重背包比完全背包多了个数的限制条件
没有用优化：SF错误
#include<bits/stdc++.h>
using namespace std;
//6 多重背包问题 III
const int N=3010;
int f[N];
int n,m;
int w[N],v[N],s[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i]>>s[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k <= s[i] && k*v[i] <= j;k++)
{
f[j]=max(f[j],f[j-v[i]*k]+w[i]*k);
}
}
}
cout<<f[m]<<endl;
}
//1051最大的和
f数组保存从1到i，连续的子串的最大值。
rf数组保存从i到n的~
在计算f的时候，要时刻记住求的是前i个数中连续的一个最大的子串
然后用df思想思考，要么选a[i]要么不选,选ai的时候要保证前面是连续的。
因而用s这个临时变量，保存必选ai的时候的最大值。‘
#include<bits/stdc++.h>
using namespace std;
//1051最大的和
const int N=50010;
int f[N],rf[N],a[N];
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
for(int i=1; i<=n; i++)cin>>a[i];
//避免出现全都是负数，但是结果为全0
memset(f,-0x3f,sizeof f);
memset(rf,-0x3f,sizeof rf);
//找从1到n 以i结尾的连续串的最大的和是多少
int s=0;//截止到i这个位置，而且必须加上a[i]的最大值
for(int i=1; i<=n; i++)
{
//用闫氏dp的思考方式思考
//i这个点的f值，要么加上a[i]，要么不加。
//s就保存了加上ai的结果，s永远保存在运行到i的时候的位置的最大值（包含a[i]）
s=max(s,0)+a[i];//要保证是一个和a[i]连续的数
f[i]=max(s,f[i-1]);
}
s=0;
for(int i=n; i>=1; i--)
{
s=max(0,s)+a[i];
rf[i]=max(s,rf[i+1]);
}
int res=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
res=max(res,rf[i+1]+f[i]);
}
cout<<res<<endl;
}
}
898、数字三角形
第一个自己做出来的线性dp，注意为了防止出现全零的情况，一定要初始化为-0x3f3f3f3f
在找上一个状态的时候，注意下标不要错。
#include<bits/stdc++.h>
using namespace std;
//898 数字三角形
const int N=510;
int f[N][N];
int a[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
f[i][j]=-0x3f3f3f3f;
}
}
f[1][1]=a[1][1];
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(j==1)
{
f[i][j]=f[i-1][1]+a[i][j];
}
else if(j==i)
{
f[i][j]=f[i-1][i-1]+a[i][j];
}
else
{
f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
}
}
}
int res=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
res=max(res,f[n][i]);
}
cout<<res<<endl;
}
//895、最长上升子序列
没有严格按照岩石地皮分析法思考导致没想出来。
数组表示某个点之前的点，构成的子序列的最长长度。
状态的计算：循环之前的所有以小于i的点为结尾的子序列的长度，然后根据大小是否加一，是否更新。
#include<bits/stdc++.h>
using namespace std;
//895 最长上升子序列
const int N=1010;
int n;
int f[N],a[N];
int main()
{
cin >> n;
for(int i=1;i<=n;i++)cin>>a[i];
memset(f,0x3f,sizeof f);
//memset(a,0x3f,sizeof a);
f[1]=1;
for(int i=2;i<=n;i++)
{
f[i]=1;
for(int j=1;j<=i;j++)
{
if(a[i]>a[j])
{
if(f[j]+1>f[i])
{
f[i]=f[j]+1;
}
}
}
}
cout<<f[n]<<endl;
}
897 最长公共子序列
状态计算看的题解，如果相等就是f[i-1][j-1]+1
如果不等，其中至少有一个不再公共子序列里面。
max(f[i-1][j],f[i][j-1],f[i-1][j-1]) 根据常识知道f[i-1][j-1]<=(f[i-1][j],f[i][j-1]的任意一个)
#include<bits/stdc++.h>
using namespace std;
//897 最长公共子序列
const int N=1010;
int n,m;
int f[N][N];
char a[N],b[N];
int main()
{
cin >> n>>m;
scanf("%s",a+1);
scanf("%s",b+1);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(a[i]==b[j])
{
f[i][j]=f[i-1][j-1]+1;
}
else
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
}
}
}
cout<<f[n][m]<<endl;
}
