読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

abc 032

D問題

N < 30 のとき

void solve1()
{
  int n1 = N/2;
  int n2 = (N + 1)/2;
  vector<pair<ll,ll> > a;
  REP(i,1<<n1)
  {
    ll sw = 0, sv = 0;
    REP(j,n1) if(i & 1 << j)
    {
      sw += w[j];
      sv += v[j];
    }
    a.emplace_back(sw,sv);
  }
  sort(a.begin(),a.end());
  int m = 0;
  FOR(i,1,(1<<n1)-1)
    if(a[m].second < a[i].second) a[m++] = a[i];
  ll ret = 0;
  REP(i,1<<n2)
  {
    ll sw = 0, sv = 0;
    REP(j, n2) if (i & 1 << j)
    {
      sw += w[j+n1];
      sv += v[j+n1];
    }
    if(sw <= W)
    {
      ll tv = (lower_bound(a.begin(),a.begin()+m,make_pair(W-sw, LLINF))-1)->second;
      ret = max(ret,sv+tv);
    }
  }
  cout << ret << endl;
}

価値の最大値が1000以下の時

const int NMAX = 210;
const int VMAX = 1010;

void solve2()
{
  const int NV = NMAX*VMAX;
  ll dp[NV];
  fill_n(dp,NV,LLINF);
  dp[0] = 0;
  REP(i,N) DOWN(j,NV-1,v[i])
    dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
  DOWN(i,NV-1,0) if(dp[i] <= W)
  {
    cout << i << endl;
    return;
  }
}

重さの最大値が1000以下の時

const int NMAX = 210;
const int WMAX = 1010;
void solve3()
{
  const int NW = NMAX*WMAX;
  ll dp[NW];
  fill_n(dp,NW,0);
  REP(i,N) DOWN(j,W,w[i])
    dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
  ll ret = 0;
  FOR(i,0,W) ret = max(dp[i],ret);
  cout << ret << endl;
}