题目链接：

题意：中文题目，见链接

题解：设 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 
     
       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
      
        9 #define pb push_back10 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 local47     freopen("data.txt", "r", stdin);48 #endif49     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\n",dp[n]);68     }69     return 0;70 }