洛谷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
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;
}

TRANSLATE with x

English

TRANSLATE with

COPY THE URL BELOW



Back

EMBED THE SNIPPET BELOW IN YOUR SITE



Enable collaborative features and customize widget: Bing Webmaster Portal

Back

本文来自博客园，作者：zjsqwq，转载请注明原文链接：https://www.cnblogs.com/zjsqwq/p/16353744.html