AtCoder Beginner Contest 306 - D - Poisonous Full-Course

Solost

2023 年 06 月 25 日

182 次浏览

暂无评论

1162字数

题目题解

## 题目连接

[链接](https://atcoder.jp/contests/abc306/tasks/abc306_d)

## 题目大意

有N个物品，0物品无毒，1物品有毒，你不能连续吃两次有毒的东西，吃完没毒的就会从前一种状态转移到现在吃的东西的状态，问你吃了的东西的总价值是多少。

## 题解

刚开始想的是双指针扫描，但是会有一个问题，如果前面选的是0，现在选了一个1，可能后面只有一个0，导致你选了10这种情况反而会使价值减少，所以排除双指针这种写法。改为dp

* `x[i] == 1, f[i][0] = f[i - 1][0], f[i][1] = max(f[i - 1][0] + y, f[i - 1][1]`
* `x[i] == 0, f[i][0] = max(f[i - 1][0], f[i - 1][1] + y,f[i - 1][0] + y, f[i][1] = f[i - 1][1] `

## 代码

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 3e5 + 10;
ll f[N][2];
pll a[N];
void solve()
{
    int n;
    cin >> n;
    ll sum = 0, p = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    for (int i = 1; i <= n; i++) {
        ll &x = a[i].x, &y = a[i].y;
        if(x == 1){
            f[i][0] = f[i - 1][0];
            f[i][1] = max(f[i - 1][1], f[i - 1][0] + y);
        }
        else{
            f[i][0] = max(f[i - 1][0], max(f[i - 1][0] + y, f[i - 1][1] + y));
            f[i][1] = f[i - 1][1];
        }
    }
    cout << max(f[n][0], f[n][1]) << endl;
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 06 月 25 日