多重背包的二进制优化、单调栈二分dp

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int M = 2e3 + 9;
int dp[M];
void solve() {
  int m, n;
  cin >> m >> n;
  for (int i = 1; i <= n; i++) {
    int s, w, v;
    cin >> s >> w >> v;
    vector<int> vec;
    int x = 1;
    while (s >= x) vec.push_back(x), s -= x, x <<= 1;
    if (s) vec.push_back(s);
    for (auto& k : vec) {
      for (int j = m; j >= 0; j--) {
        if (j >= k * v)
          dp[j] = max(dp[j], dp[j - k * v] + k * w);
        else
          dp[j] = dp[j];
      }
    }
  }
  cout << dp[m];
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 9;
int a[N], dp[N];

void solve() {
  int n;
  cin >> n;
  int max_n = 1;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    dp[i] = 1;
    for (int j = i - 1; j > 0; j--) {
      if (a[i] >= a[j]) dp[i] = max(dp[j] + 1, dp[i]);
      max_n = max(max_n, dp[i]);
    }
  }
  cout << max_n;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 9;
int a[N];
int stk[N], top;
void solve() {
  int n;
  cin >> n;
  int ans = 0;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) {
    int pos = upper_bound(stk + 1, stk + 1 + top, a[i]) - stk;
    if (pos == top + 1) top++;
    stk[pos] = a[i];
    ans = max(ans, top);
  }
  cout << ans;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 9;
int a[N];
int stk[N], top;
void solve() {
  int ans = 0;
  int n = 0;
  while (cin >> a[++n]) {
  }
  n--;
  for (int i = 1; i <= n; i++) {
    int pos = upper_bound(stk + 1, stk + 1 + top, a[i],
                          [](const int& u, const int& v) { return u > v; }) -
              stk;
    if (pos == top + 1) top++;
    stk[pos] = a[i];
    ans = max(ans, top);
  }
  cout << ans << endl;
  top = 0, ans = 0;
  for (int i = 1; i <= n; i++) {
    int pos = lower_bound(stk + 1, stk + 1 + top, a[i]) - stk;
    if (pos == top + 1) top++;
    stk[pos] = a[i];
    ans = max(ans, top);
  }
  cout << ans;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}