dp知识点:
多重背包的二进制优化:
本来是一个一个拆,再一个一个组成,现在将其变化为以二进制形式拆,再以二进制形式组成,以达成log级别
https://www.starrycoding.com/problem/76
// 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;
}线性dp:
https://www.starrycoding.com/problem/77
暴力:O(N^2)
// 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;
}https://www.starrycoding.com/problem/48
运用栈将状态保存,不断优化最优位置
// 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;
}https://www.starrycoding.com/problem/78
// 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;
}