vp中途突然拉肚子>_<
D - Poisonous Full-Course
D - Poisonous Full-Course (atcoder.jp)
题意
一个人初始是健康的,现在有n道菜摆在他面前,每道菜都有自已的美味值,但是有些菜是有毒的,有些菜是无毒的。如果他在健康状态吃了有毒的菜就会变成中毒状态,如果他在中毒状态吃了无毒的菜就会变回健康状态,如果他在中毒状态吃了有毒的菜就会死亡。
面对依次上前的n道菜,他可以选择吃或跳过。求得在避免死亡的状态下获得最大的美味值。
思路
简单的dp,设dp[i][j]为在第i道菜时处于j状态下的最大美味值,j为0是健康,j为1是中毒。可以推得状态转移方程,当菜无毒时,dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][0]) + y), dp[i][1] = dp[i-1][1]。当菜有毒时,dp[i][1] = max(dp[i-1][1], dp[i-1][0] + y), dp[i][0] = dp[i-1][0]。
还可用滚动数组优化,详见代码。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
array<ll, 2> dp;
for(int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
if(x == 0) {
dp[0] = max(dp[0], max(dp[1], dp[0]) + y);
} else {
dp[1] = max(dp[1], dp[0] + y);
}
}
cout << max(dp[0], dp[1]) << "\n";
return 0;
}
E - Best Performances
E - Best Performances (atcoder.jp)
题意
初始时有一个全为零的序列,然后进行若干次更改,每次更改把某个下标的数改成另一个数,每次更改后输出序列中前k个最大的数的和。
思路
用两个multiset维护前k个最大的元素和剩下的元素,再用一个数组记录真实下标对应的值,然后模拟即可。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, q;
cin >> n >> k >> q;
multiset<int> s1, s2;
vector<int> p(n + 1);
for(int i = 0; i < n; i++) {
if(i < n - k) {
s1.insert(0);
} else {
s2.insert(0);
}
}
if(s1.empty()) {
s1.insert(-1); //防止段错误
}
ll ans = 0;
while(q--) {
int x, y;
cin >> x >> y;
auto it = s2.find(p[x]);
if(it != s2.end()) {
ans -= p[x];
s2.erase(it);
if(y >= *prev(s1.end())) {
ans += y;
s2.insert(y);
} else {
auto tmp = prev(s1.end());
ans += *tmp;
s2.insert(*tmp);
s1.insert(y);
s1.erase(tmp);
}
} else {
auto it = s1.find(p[x]);
if(y >= *s2.begin()) {
s2.insert(y);
ans += y;
auto tmp = s2.begin();
s1.insert(*tmp);
ans -= *tmp;
s2.erase(tmp);
s1.erase(it);
} else {
s1.erase(it);
s1.insert(y);
}
}
p[x] = y;
cout << ans << "\n";
}
return 0;
}
- Atcoder Beginer Contest 306atcoder beginer contest 306 beginner atcoder contest 306 306 beginner atcoder contest atcoder abc 306 def contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328