蓝桥杯每日一题（背包dp,线性dp）

//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;
}