# [SMOJ2073]Bug

xiaoxiao2021-02-28  9

s(k)=min{fk,fi+(fjfk)} if i<k<j

s(k)=fk(fjfi)=fi+(fkfj) if jk

#include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> using namespace std; const int MAXN = 1e5 + 100; int N; long long len[MAXN], f[MAXN]; int main(void) { freopen("2073.in", "r", stdin); freopen("2073.out", "w", stdout); scanf("%d", &N); f[0] = 0LL; for (int i = 1; i < N; i++) { scanf("%lld", &len[i]); f[i] = f[i - 1] + len[i]; } long long ans = 214748364700000LL; for (int i = 1; i < N; i++) for (int j = i + 1; j <= N; j++) { long long m = 0; for (int k = 2; k <= N; k++) { long long c; if (k <= i) c = f[k - 1]; //A 部分 else if (k < j) c = min(f[k - 1], f[i - 1] + (f[j - 1] - f[k - 1])); //B 部分 else c = f[i - 1] + (f[k - 1] - f[j - 1]); //C 部分 m = max(m, c); } ans = min(ans, m); } printf("%lld\n", ans); return 0; }

s(j)=min{fj,fifj} if j<i

#include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> using namespace std; const int MAXN = 1e5 + 100; int N; long long len[MAXN], f[MAXN]; long long solve(int k) { //二分找出：对于右入口放在k时，两种方法的分界点 int l = 2, r = k; //[l, r) 左闭右开 while (l + 1 < r) { int mid = l + r >> 1; if ((f[k] - f[mid]) <= f[mid]) r = mid; else l = mid; } return l + 1 == k ? f[l] : max(f[l], f[k] - f[r]); //注意不用走回头路的边界情况 } int main(void) { freopen("2073.in", "r", stdin); freopen("2073.out", "w", stdout); scanf("%d", &N); for (int i = 1; i < N; i++) scanf("%lld", &len[i]); f[1] = 0LL; //前缀和 for (int i = 2; i <= N; i++) f[i] = f[i - 1] + len[i - 1]; long long ans = f[N]; for (int i = 2; i <= N; i++) ans = min(ans, max(f[N] - f[i], solve(i))); //还要考虑 C 部分的情况 printf("%lld\n", ans); return 0; }