洛谷 P6563 [SBCOI2020] 一直在你身旁 解题报告

洛谷 P6563 [SBCOI2020] 一直在你身旁 解题报告

对这道神仙题目的理解还不是很深刻，先贴两个学习的题解吧QwQ

Sol

https://www.luogu.com.cn/blog/2019-13-32-25-61-61/solution-p6563

Code

https://www.luogu.com.cn/blog/105254/solution-p6563

MyCode

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
    int x = 0; char ch = getchar(); bool sgn = 0;
    while (ch < '0' || ch > '9') sgn |= ch == '-', ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + (ch & 15), ch = getchar();
    return sgn ? -x : x;
}
#undef int
const int MN = 7100 + 10;
const long long INF = 0x7fffffff;
pair<long long, int> q[MN];
int head, tail;
inline long long front() {
    return head < tail ? q[head].first : INF;
}
inline void modify_front(int x) {
    while (head < tail && q[head].second >= x) head++;
}
inline void push(pair<long long, int> x) {
    while (head < tail && q[tail - 1].first >= x.first) tail--;
    q[tail++] = x;
}
long long dp[MN][MN];
int T, n, a[MN];
signed main() {
    T = read();
    while (T--) {
        n = read();
        for (int i = 0; i < n; ++i) a[i] = read();
        for (int r = 1; r < n; ++r) {
            head = tail = 0;
            for (int l = r - 1, mid = r - 1; l >= 0; --l) {
                while (mid >= l && dp[l][mid] >= dp[mid + 1][r]) mid--;
                modify_front(mid + 1);
                dp[l][r] = min(dp[l][mid + 1] + a[mid + 1], front());
                if (l > 0) push(pair<long long, int>(dp[l][r] + a[l - 1], l - 1));
            }
        }
        cout << dp[0][n - 1] << 'n';
    }
    return 0;
}