可达性dp

基础版（只考虑是否可达的bool数据类型）

由题意知，无论如何如何， 0个橘子是一定可以达到的，设dp[0] = 1;

由题意可知，若节点 i 可达，则节点 i-6 和节点 i-8 可达。则设计出状态转移方程dp[i] = dp[i] | dp[i-6] | dp[i-8];

依赖关系为：大下标节点依赖小下标节点。

标准（记录最少的次数）

设计状态：令dp1[i]表示是否能到达，dp2[i]表示到达所需要的最小次数。

可知状态转移方程有

dp1[i] = dp1[i] | dp1[i-6] | dp1[i-8];
dp2[i] = INF;
if(dp1[i-6]) { dp2[i] = min(dp2[i] , dp1[i-6] + 1); }
if(dp1[i-8]) { dp2[i] = min(dp2[i] , dp1[i-8] + 1); }

此外，也可以当作完全背包来理解。

现实做题中，dp1与dp2完全可以使用一个dp数组来表示。

// #pragma GCC optimize("O3")
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
// using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
// using lll = __int128;
using ldouble = long double;
#define INF (LLONG_MAX / 2 + INT_MAX / 2)
#define u_map unordered_map
#define u_set unordered_set
#define m_map multimap
#define m_set multiset
#define p_que priority_queue

void isolat() {
    int n;
    cin >> n;

    vector<int> dp((int)1e5 + 1, -1);
    dp[0] = 0;
    for (int i = 0; i <= (int)1e5; ++i) {
        if (i < 6) {
            continue;
        }
        if (dp[i - 6] >= 0) {
            dp[i] = dp[i - 6] + 1;
        }
    }
    for (int i = 0; i <= (int)1e5; ++i) {
        if (i < 8) {
            continue;
        }
        if (dp[i - 8] >= 0) {
            int val = dp[i - 8] + 1;
            if(dp[i] < 0){
                dp[i] = val;
            }else{
                dp[i] = min(dp[i],val);
            }
        }
    }

    cout << dp[n] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int _ = 1;
    // cin >> _;
    while (_--) {
        isolat();
    }
    return 0;
}

第一次写题解，有错误或做的不好的地方请指出，谢谢。