daily 3

背包专场了属于是

CF 741B

并查集+分组背包
具体不多说了，比较简单

void solve(){
  int n,m,w;
  cin>>n>>m>>w;
  vector<int>dp(w+1),fa(n+1),b(n+1),we(n+1);
  function<int(int x)>f=[&](int x){
        return fa[x]==x?x:fa[x]=f(fa[x]);
  };
  iota(fa.begin(),fa.end(),0);
  for(int i=1;i<=n;++i){
    cin>>we[i];
  }
  for(int i=1;i<=n;++i){
    cin>>b[i];
  }
  for(int i=1;i<=m;++i){
    int u,v;
    cin>>u>>v;
    fa[f(u)]=f(v);
  }
  vector<vector<int>>fr(n+1);
  for(int i=1;i<=n;++i){
    fr[f(i)].push_back(i);
  }
  for(int i=1;i<=n;++i){
    for(int siz=w;siz>=0;--siz){
        int W=0,B=0;
        for(int v:fr[i]){
            W+=we[v];
            B+=b[v];
            if(siz>=we[v])dp[siz]=max(dp[siz-we[v]]+b[v],dp[siz]);
        }
        if(siz>=W){
            dp[siz]=max(dp[siz-W]+B,dp[siz]);
        }
    }
  }
  cout<<dp[w]<<'\n';
  return;
}

CF 19B
我们可以把这个问题转化为01背包，把每个物品看作容量为t[i]+1,代价为c[i]的新物品

void solve(){
  int n;
  cin>>n;
  vector<ll>t(n+1),c(n+1);
  ll w=0;
  for(int i=1;i<=n;++i){
    cin>>t[i]>>c[i];
    ++t[i];
    w=max(t[i],w);
  }
  w+=n;
  vector<ll>dp(w+1,1e16);
  dp[0]=0;
  for(int i=1;i<=n;++i){
    for(int v=w;v>=t[i];--v){
        dp[v]=min(dp[v],dp[v-t[i]]+c[i]);
    }
  }
  ll ans=1e16;
  for(int i=n;i<=w;++i){
    ans=min(ans,dp[i]);
  }
  cout<<ans<<'\n';
  return;
}

CF 577B

没啥好说的了，抽屉原理+dp(甚至感觉都不像背包)

void solve(){
  int n,m;
  cin>>n>>m;
  if(n>m){
    cout<<"YES\n";
    return;
  }
  vector<int>a(n+1);
  for(int i=1;i<=n;++i){
    cin>>a[i];
    a[i]%=m;
  }
  vector dp(m+1,vector<int>(m+1));
  bool f=false;
  for(int i=1;i<=n;++i){
    dp[i][a[i]]=1;
    for(int j=1;j<=m;++j){
        dp[i][j]|=dp[i-1][j];
        dp[i][(j+a[i])%m]|=dp[i-1][j];
    }
    f|=dp[i][0];
    if(f)break;
  }
  cout<<(f?"YES":"NO")<<'\n';
  return;
}