Блог пользователя kunal_rai

Автор kunal_rai, история, 3 года назад, По-английски

The total number of elements in v can be up to N

const int N = 1e3;
int dp[N][N];
vector<vector<int>> v(N);

int go(int ind,int k) {
  if(ind == N)
    return 0;

  if(dp[ind][k] != -1)
    return dp[ind][k];

  int ans = go(ind + 1,k);

  for(int i: v[ind]) {
    if(k - i >= 0)
      ans = max(ans,go(ind + 1,k - i) + i);
  }

  return dp[ind][k] = ans;
}
  • Проголосовать: нравится
  • -23
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

its O(N*N*K) I think.