题目链接：https://www.nowcoder.com/acm/contest/94/G
题意：中文题目，见链接
题解：设 sum[i] 为 a[i] 的前缀和，可得公式
dp[i] = min( dp[j] + ( sum[i] - sum[j] - b[i] ) ^ 2 )
= min( dp[j] + sum[j] ^ 2 + 2 * ( sum[i] - b[i] ) * ( sum[i] - sum[j] ) + sum[i] - b[i] ) ^ 2
设 y = dp[j] + sum[j] ^ 2，k = sum[i] - b[i]，x = sum[i] - sum[j]，b = sum[i] - b[i] ) ^ 2
有 y = 2 * k * x + b
因为 k 的正负不确定，但 y 和 x 符合单调性，故可以二分找出第一个比当前点斜率大的点来维护下凸性（注意最好手写二分，使用lower_bound可能会出错）
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define ull unsigned long long 5 #define mst(a,b) memset((a),(b),sizeof(a)) 6 #define mp(a,b) make_pair(a,b) 7 #define pi acos(-1) 8 #define pii pair<int,int> 9 #define pb push_back 10 const int INF = 0x3f3f3f3f; 11 const double eps = 1e-6; 12 const int MAXN = 1e6 + 10; 13 const int MAXM = 1e3 + 10; 14 const ll mod = 100000073; 15 16 int n,tail; 17 int q[MAXN]; 18 ll a[MAXN],b[MAXN],sum[MAXN],dp[MAXN]; 19 double k[MAXN]; 20 21 ll sqr(ll x) { 22 return x * x; 23 } 24 25 ll getup(int j,int k) { 26 return dp[j] + sqr(sum[j]) - (dp[k] + sqr(sum[k])); 27 } 28 29 ll getdown(int j,int k) { 30 return 2ll * (sum[j] - sum[k]); 31 } 32 33 int findd(double x) { 34 int l = 0, r = tail - 1, ans = 0; 35 while(l <= r) { 36 int mid = (l + r) >> 1; 37 ll up = dp[q[mid]] + sqr(sum[q[mid]]) - (dp[q[mid - 1]] + sqr(sum[q[mid - 1]])); 38 ll down = 2.0 * (sum[q[mid]] - sum[q[mid - 1]]); 39 if(up <= down * x) l = mid + 1, ans = mid; 40 else r = mid - 1; 41 } 42 return q[ans]; 43 } 44 45 int main() { 46 #ifdef local 47 freopen("data.txt", "r", stdin); 48 #endif 49 sum[0] = dp[0] = 0; 50 while(~scanf("%d",&n)) { 51 for(int i = 1; i <= n; i++) { 52 scanf("%lld",&a[i]); 53 sum[i] = sum[i - 1] + a[i]; 54 } 55 for(int i = 1; i <= n; i++) scanf("%lld",&b[i]); 56 tail = 0; 57 q[tail++] = 0; 58 for(int i = 1; i <= n; i++) { 59 int id = findd(1.0 * (sum[i] - b[i])); 60 dp[i] = dp[id] + sqr(sum[i] - sum[id] - b[i]); 61 while(1 < tail && getup(q[tail - 1],q[tail - 2]) * getdown(i,q[tail - 1]) >= getup(i,q[tail - 1]) * getdown(q[tail - 1],q[tail - 2])) 62 tail--; 63 if(getdown(i,q[tail - 1]) == 0) k[tail] = 1e18; 64 else k[tail] = 1.0 * getup(i,q[tail - 1]) / getdown(i,q[tail - 1]); 65 q[tail++] = i; 66 } 67 printf("%lld ",dp[n]); 68 } 69 return 0; 70 }