[DP 01背包/差值DP 存在性]小M和天平

[DP 01背包/差值DP 存在性]小M和天平

题目

室友大佬去玩了蓝桥杯，听室友回寝口述的题目，然后水群的时候群友说和这题差不多就做一下。感觉和不久前做的差值DP有点关系。

思路

两种思路，状态转移其实差不多。
01背包
方案存在性DP，利用或运算连接
要么全部放一边，另外一边不放，这就裸的01DP
两边都放，假设都放左边，枚举右边体积，看是否存在

差值DP

其实就是问哪些差值是可达的

差值DP例题：​​洛谷：塔​

状态转移

放轻的超过重的为例

状态转移其实差不了多少就不重复写代码了，差值DP应该也可以压掉一维

室友说蓝桥杯问可凑出的数的数量，数据量比较小，那就暴力遍历统计一遍，大概？

代码

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1e5+10;
typedef long long LL;
LL a[N];
bool f[M];
LL sum;
int n,m;
int main()
{
    while(cin>>n)
    {
        memset(f,0,sizeof f);
        sum=0;
        for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}
        
        f[0]=1;
        for(int i=1;i<=n;i++)
            for(int j=sum;j>=a[i];j--)
                f[j]|=f[j-a[i]];
     
        for(int i=1;i<=n;i++)
            for(int j=a[i];j<=sum;j++)
                f[j-a[i]]|=f[j];
        
        cin>>m;
        while(m--)
        {
            int x;cin>>x;
            if(x>sum)puts("NO");
            else
            {
                if(f[x])puts("YES");
                else puts("NO");
            }
        }
    }
    return 0;
}

差值DP

// Problem: 小M和天平
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/13586
// Memory Limit: 262144 MB
// Time Limit: 4000 ms
// FishingRod

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
//#define MULINPUT
/*DATA & KEY
N 1 100
W 1 100
M 1 1E3
K 1 1E9
*/
int T;
const int N=105,M=1e4+10;
int a[N];
bool f[N][M];
void solve(int C)
{
  //NEW DATA CLEAN
  
  //NOTE!!!
  int n,m;
  while(cin>>n)
  {
    memset(f,0,sizeof f);
    LL sum=0;
    for(int i=1;i<=n;i++){cin>>a[i],sum+=a[i];}
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
      for(int j=0;j<=sum;j++)
      {
        f[i][j]|=f[i-1][j];
        if(j+a[i]<=sum)f[i][j]|=f[i-1][j+a[i]];
        if(j-a[i]>0)f[i][j]|=f[i-1][j-a[i]];
        else f[i][j]|=f[i-1][a[i]-j];
      }
    }
    cin>>m;
    while(m--)
    {
      int k;cin>>k;
      if(k>sum)puts("NO");
      else
      {
        if(f[n][k])puts("YES");
        else puts("NO");
      }
    }
  }
  
}

int main()
{
  #ifdef MULINPUT
    scanf("%d",&T);
    for(int i=1;i<=T;i++)solve(i);
  #else
    solve(1);
  #endif
  return 0;
}