简单
题意描述：有 \(2n\) 个数分别分为 \(n\) 组，即每组两个数，要求累加每组的较小一数，最大化这个答案。
一道贪心题，直接将原序列排序，然后输出每两个数中的前一个数即可。
#include <bits/stdc++.h>
#define MAXN 100000 + 10
using namespace std;
inline int read() {
int f = 1, w = 0; char ch = getchar();
while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') w = w * 10 + ch - '0', ch = getchar();
return w * f;
}
int n, a[2 * MAXN];
long long ans;
int main() {
//freopen("simple.in", "r", stdin);
//freopen("simple.out", "w", stdout);
n = read();
for (int i = 0; i < 2 * n; i++) {
a[i] = read();
}
sort(a, a + 2 * n);
for (int i = 0; i < 2 * n; i += 2) {
ans += a[i];
}
printf("%lld", ans);
return 0;
}
刷题
题意：给定一串数列，要求从第一个点起跳，跳到最后一个点。每次询问给出最多能跳的长度。如果当前点上的数比要跳到的点上的数小则步数不变，否则步数+1。初始步数为0。要求最小化步数。
可以用单调队列解决。维护一个单调队列，从2开始遍历每一个点，循环删除队首不合法的点（即无法在最大可跳长度内跳到当前点），遍历到的点的DP（步数）值即为队列首的DP值，如果当前点数值小于队首的点的数值，那么还要再+1。 再循环删除队尾不合法的点，即队尾的点的DP值大于当前节点DP值的点。如果DP值相等，则比较点上的数值，如果队尾节点数值更小则删掉，因为不利于后面的点不费步数地跳跃（值更高的显然更优）。最后让当前节点进队即可。
可以手写队列，也可以用stl里的deque。时间复杂度 \(O(n)\) 。
#include <bits/stdc++.h>
#define MAXN 1000010
#define db printf("\nnaive\n")
using namespace std;
typedef pair<int, int> P;
inline int read() {
int f = 1, w = 0;
char ch = getchar();
while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') w = w * 10 + ch - '0', ch = getchar();
return w * f;
}
int n, diff[MAXN], q, k;
int dp[MAXN];
bool cmp(int a, int b) {
return dp[a] == dp[b] ? diff[a] > diff[b] : dp[a] < dp[b];
}
deque<int> que;
int main() {
//freopen("jump.in", "r", stdin);
//freopen("jump.out", "w", stdout);
n = read();
for (int i = 1; i <= n; i++) {
diff[i] = read();
}
q = read();
while (q--) {
que.clear();
k = read();
que.push_back(1);
for (int i = 2; i <= n; i++) {
while (!que.empty() && que.front() < i - k) que.pop_front();
dp[i] = dp[que.front()] + (diff[que.front()] <= diff[i]);
while (!que.empty() && cmp(i, que.back())) que.pop_back();
que.push_back(i);
}
printf("%d\n", dp[n]);
}
return 0;
}
礼物
题意：有 \(n\) 个物品以及 \(n\) 张优惠券，每个物品都有给定的价格，且可以用指定的一张优惠券优惠对应的价格。但是优惠券使用有依赖条件，即：如果要使用第 \(i\) 张优惠券，就必须使用第 \(p_i\) 张优惠券（ \(p_i\) 题目给定）。第一个物品没有依赖关系，可以直接使用它的优惠券。现有一定量的金钱，问最多能买多少个物品。
因为优惠券有依赖关系，且第一个物品没有依赖，所以我们以第一个物品为根节点，以优惠券依赖为边建成一棵 \(n\) 个节点的树。
考虑一下dp做法。既然 \(S\) 太大，那么我们不选择维护物品个数，而选择去维护金钱。现在考虑的是如何转移。
既然是个树型结构，那么就要对子树下手。对于每个节点，考虑一下它的子树的选择情况。很明显，如果子树使用优惠券，那么当前节点必须也使用优惠券（根据题意）。如果子树不使用优惠券，那么可能是买也可能是不买，这时候只能转移到父亲的不使用优惠券状态。所以我们可以构造出 dp 数组 \(dp[i][j][k]\) ， 表示当前考虑到第 \(i\) 个节点，子树中买了\(j\) 个，当前节点是否使用优惠券（ \(k\) 为 1 时使用，反之则不使用）。则：
\[dp[i][j + k][0] = \min (dp[i][j + k][0] , dp[i][j][0] + dp[son(i)][k][0]\] \[dp[i][j + k][1] = \min(dp[i][j + k][1], dp[i][j][1] + \min(dp[son(i)][k][0], dp[son(i)][k][1]))\]其中， \(k\) 为枚举的子树中购买的个数。采用由根到叶子节点的递归算法，那么可以由下往上处理出所有节点的 dp 值。叶子节点即边界，\(k = 0\) 时价格为原价，反之则为优惠后的价格。会发现当前节点如果不使用优惠券，那么状态只能从子树中不使用优惠券（可能是买，可能是不买）的状态转移而来。而如果使用优惠券，那么则可以从子树中使用优惠券（买）以及不使用优惠券（不买）中转移而来。
但是光这样看，复杂度好像是 \(n^3\) 级别的。毕竟要更新所有的子树，再对当前节点进行更新，这样的话当前节点更新的代价就是当前节点的子节点数量乘以每一个子树的子节点数量。
可以考虑一种优化。我们每次只对一个子树进行统计和转移，完成后将此子树“合并”到当前节点，也就是它的父亲中。那么，这样一来，原来单个节点的接近 \(n^2\) 的操作代价就降低到了 \(Si * S_{son(i)}\) 级别，\(S_i\) 是一个累加的过程，从1到 \(\sum S_{son(i)}\) 。总的时间复杂度 \(n^2\) 。
代码如下：
#include <bits/stdc++.h>
#define MAXN 5005
using namespace std;
typedef long long ll;
ll d[MAXN][MAXN][2];
int n, S, v[MAXN], m[MAXN], s[MAXN];
vector<int> G[MAXN];
void dfs(int x) {
s[x] = 1;
d[x][0][0] = 0;
d[x][1][0] = v[x];
d[x][1][1] = v[x] - m[x];
for (int i = 0; i < (int)G[x].size(); i++) {
int t = G[x][i];
dfs(t);
//如果把s[x] += s[t]放到这里，复杂度就升为n^3
for (int j = s[x]; j >= 0; j--)
for (int k = s[t]; k >= 1; k--) {
d[x][j + k][0] = min(d[x][j + k][0], d[x][j][0] + d[t][k][0]);
d[x][j + k][1] = min(d[x][j + k][1], d[x][j][1] + min(d[t][k][0], d[t][k][1]));
}
s[x] += s[t];
}
}
int main() {
//freopen("gift.in", "r", stdin);
//freopen("gift.out", "w", stdout);
scanf("%d%d%d%d", &n, &S, &v[1], &m[1]);
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) {
d[i][j][0] = d[i][j][1] = 1e18;
}
}
for (int i = 2, a; i <= n; i++) {
scanf("%d%d%d", &v[i], &m[i], &a);
G[a].push_back(i);
}
dfs(1);
for (int i = n; i >= 0; i--) if(d[1][i][0] <= S || d[1][i][1] <= S) {
printf("%d", i);
break;
}
return 0;
}