题目：

一个斜率优化+CDQ好题

分析：

先吐槽一下题意：保留房子反而要给赔偿金是什么鬼哦……

第一问是一个经典问题。直接求原序列的最长上升子序列是错误的。比如\(\{1,2,2,3\}\)，选择\(\{1,2,3\}\)不改变后会发现无论如何修改都无法变成一个严格上升序列。只能选择\(\{1,2\}\)，把原序列改成\(\{1,2,3,4\}\)。

考虑对于两个数\(a_i\)和\(a_j(j<i)\)，\(a_i\)能接在\(a_j\)后面的充要条件是\(a_i-a_j\geq i-j\)（这样中间才能塞下\(i-j-1\)个数形成上升序列）。移项得到\(a_i-i\geq a_j-j\)，所以应该把每个数减去它的编号作为权值然后求最长非降子序列。由于要求美观度为正整数，所以若\(a_i-i<0\)，则\(i\)不能作为序列的开端。下面的代码展示了\(O(nlog_2n)\)求法（其中\(c[i]=a[i]-i\)，\(f[i]\)表示以\(i\)结尾的最长非降子序列的长度）。

int solve(){    int ans = 0;    memset(tmp, INF, sizeof(int[n + 1]));    for (int i = 1; i <= n; i++)    {        if (c[i] < 0)            f[i] = 0;        else        {            int pos = upper_bound(tmp + 1, tmp + ans + 1, c[i]) - tmp;            tmp[pos] = c[i];            ans = max(ans, pos);            f[i] = pos;        }        v[f[i]].push_back(i);    }    return ans;}

然后来看第二问。设\(dp[i]\)为将前\(i\)个数变成单调上升序列的最小总花费。则\(dp[i]\)可以由\(dp[j]\)转移而来的必要条件是\(i>j\)，\(a[i]-i>a[j]-j\)且\(f[i]=f[j]+1\)（若\(f[i]>f[j]+1\)，则不满足“保留最多的旧房子”；若\(f[i]<f[j]+1\)，说明你\(f[i]\)算错了）。

转移时，最优解显然是把\(a[k](j<k<i)\)变成一个以\(a[j]+1\)为首项，公差为\(1\)的等差数列。由于\(a[i]-i>a[j]-j\)，所以改完以后一定有\(a[i-1]<a[i]\)

\[dp[i]=min\{dp[j]+\frac{[a[j]+1+a[j]+(i-j-1)]\times(i-j-1)}{2}+a[i]+b[i]\}\]

整理一下，得到：

\[dp[i]=min\{dp[j]+a[j]\times(i-j-1)+\frac{i(i-1)}{2}+\frac{j(j+1)}{2}+-ij+a[i]+b[i]\}\]

可以根据\(f[i]\)分层，一起处理所有\(f[j]=k-1\)的\(j\)对\(f[i]=k\)的\(i\)的贡献。下面考虑每一层的情况。

未完待续……

代码：

方便起见，在序列首加一个\(0\)（\(a[0]=f[0]=0\)）。这样可以保证改造后美观度为正（因为\(f[i]=1\)的\(dp[i]\)必然从\(dp[0]\)转移而来）；在序列尾加一个无穷大作为\(a[n+1]\)，\(dp[n+1]-a[n+1]\)即为答案。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;namespace zyt{    template
         
           inline void read(T &x) { char c; bool f = false; x = 0; do c = getchar(); while (c != '-' && !isdigit(c)); if (c == '-') f = true, c = getchar(); do x = x * 10 + c - '0', c = getchar(); while (isdigit(c)); if (f) x = -x; } template
          
            inline void write(T x) { static char buf[20]; char *pos = buf; if (x < 0) putchar('-'), x = -x; do *pos++ = x % 10 + '0'; while (x /= 10); while (pos > buf) putchar(*--pos); } typedef long long ll; typedef long double ld; const int N = 1e5 + 10, INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fLL; int n, a[N], b[N], c[N], f[N], tmp[N]; ll dp[N]; vector
           
             v[N]; int solve() { int ans = 0; memset(tmp, INF, sizeof(int[n + 1])); for (int i = 1; i <= n; i++) { if (c[i] < 0) f[i] = 0; else { int pos = upper_bound(tmp + 1, tmp + ans + 1, c[i]) - tmp; tmp[pos] = c[i]; ans = max(ans, pos); f[i] = pos; } v[f[i]].push_back(i); } v[0].push_back(0); return ans; } inline ll x(const int i) { return i - a[i]; } inline ll y(const int i) { return dp[i] - (ll)(i + 1) * a[i] + (ll)i * (i + 1) / 2; } inline ld ratio(const int i, const int j) { if (x(i) == x(j)) return y(i) < y(j) ? -LINF : LINF; else return (ld)(y(i) - y(j)) / (x(i) - x(j)); } struct node { int pos; bool type; bool operator < (const node &b) const { return pos < b.pos; } }arr[N]; const int CHANGE = 0, QUERY = 1; void CDQ(const int l, const int r) { if (l == r) return; int mid = (l + r) >> 1, i = l, j = mid + 1, k = l; static node tmp[N]; static int st[N]; CDQ(l, mid), CDQ(mid + 1, r); int top = 0; while (i <= mid && j <= r) { if (x(arr[i].pos) >= x(arr[j].pos)) { if (arr[i].type == CHANGE) { while (top > 1 && ratio(st[top - 2], st[top - 1]) < ratio(st[top - 1], arr[i].pos)) --top; st[top++] = arr[i].pos; } tmp[k++] = arr[i++]; } else { if (arr[j].type == QUERY && top) { int l = 0, r = top - 2, ans = top - 1; while (l <= r) { int mid = (l + r) >> 1; if (ratio(st[mid], st[mid + 1]) < arr[j].pos) r = mid - 1, ans = mid; else l = mid + 1; } dp[arr[j].pos] = min(dp[arr[j].pos], dp[st[ans]] + (ll)((a[st[ans]] << 1) + arr[j].pos - st[ans]) * (arr[j].pos - st[ans] - 1) / 2 + a[arr[j].pos] + b[arr[j].pos]); } tmp[k++] = arr[j++]; } } while (i <= mid) tmp[k++] = arr[i++]; while (j <= r) { if (arr[j].type == QUERY && top) { int l = 0, r = top - 2, ans = top - 1; while (l <= r) { int mid = (l + r) >> 1; if (ratio(st[mid], st[mid + 1]) < arr[j].pos) r = mid - 1, ans = mid; else l = mid + 1; } dp[arr[j].pos] = min(dp[arr[j].pos], dp[st[ans]] + (ll)((a[st[ans]] << 1) + arr[j].pos - st[ans]) * (arr[j].pos - st[ans] - 1) / 2 + a[arr[j].pos] + b[arr[j].pos]); } tmp[k++] = arr[j++]; } memcpy(arr + l, tmp + l, sizeof(node[r - l + 1])); } int work() { read(n); for (int i = 1; i <= n; i++) read(a[i]), c[i] = a[i] - i; for (int i = 1; i <= n; i++) read(b[i]); a[++n] = INF; c[n] = INF; int ans = solve(); write(ans - 1), putchar(' '); memset(dp, INF, sizeof(ll[n + 1])); dp[0] = 0; for (int i = 1; i <= ans; i++) { int cnt = 0; for (int j = 0; j < v[i - 1].size(); j++) if (dp[v[i - 1][j]] < LINF) arr[++cnt] = (node){v[i - 1][j], CHANGE}; for (int j = 0; j < v[i].size(); j++) arr[++cnt] = (node){v[i][j], QUERY}; sort(arr + 1, arr + cnt + 1); CDQ(1, cnt); } write(dp[n] - a[n] - b[n]); return 0; }}int main(){ return zyt::work();}