题目连接

链接

题目大意

有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]

代码

#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;
}