• 欢迎光临~

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

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

### 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
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];
inline long long front() {
}
inline void modify_front(int x) {
}
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() {
while (T--) {
for (int i = 0; i < n; ++i) a[i] = read();
for (int r = 1; r < n; ++r) {
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;
}
``````