Solution

很显然，最优情况肯定是相邻两个相连。

然后模型就跟 Luogu1484 类似了。

把两个房子看成一个坑（参考 Luogu1484），选取 $k$ 个不相邻的坑，使得权值最小。

Luogu1484 则是选取至多 $k$ 个不相邻坑，使得权值最大。

先考虑简单问题：

当$k= 1$时，肯定是选择最大的$a[i]$

当$k= 2$时，仅有两种情况选最大的 $a[i]$ 和不相邻的 $a[j]$ 或者 $a[i+1]+a[i-1]$

　　我们先选了最大的$a[i]$

　　那么怎么样才能让下一个找到的最大的 $a[j]$ 是满足条件的解呢？

　　我们把 $a[i - 1]$ 和 $a[i + 1]$ 删去，然后把 $a[i]$改为 $a[i + 1] + a[i - 1] - a[i]$，这样就满足了肯定不会单独选到 $a[i + 1]或a[i-1]$。

　　并且我们若想要选$a[i+1]和a[i-1]$且不选$a[i]$ 只需要再选一次$a[i]$即可。

在$k$更大的情况下同样适用。

然后就用链表存储 $nxt$ 与 $pre$， $Set$ 维护最大值/ 最小值。

Code

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<set>

 #define rd read()

 #define ll long long

 using namespace std;

 typedef pair<ll, int> P;

 const int N = 1e5 + ;

 const ll inf = 1e10;

 int n, k;

 int nxt[N], pre[N];

 ll a[N], ans;

 set<P> st;

 int read() {

     int X = , p = ; char c = getchar();

     for (; c > '' || c < ''; c = getchar())

         if (c == '-') p = -;

     for (; c >= '' && c <= ''; c = getchar())

         X = X *  + c - '';

     return X * p;

 }

 void del(int x) {

     nxt[pre[x]] = nxt[x];

     pre[nxt[x]] = pre[x];

 }

 int main()

 {

     n = rd; k = rd;

     for (int i = ; i <= n; ++i)

         a[i] = rd;

     n--;

     for (int i = ; i <= n; ++i)

         a[i] = a[i + ] - a[i];

     for (int i = ; i <= n; ++i)

         nxt[i] = i + , pre[i] = i - ;

     for (int i = ; i <= n; ++i)

         st.insert(P(a[i], i));

     a[] = a[n + ] = inf;

     set<P> :: iterator it;

     for (; k; --k) {

         it = st.begin();

         P tp = *it;

         int x = tp.second; ll y = a[x];

         ll t = a[pre[x]] + a[nxt[x]] - y;

         a[x] = t; ans += y;

         st.insert(P(t, x));

         st.erase(P(y, x));

         if (pre[x])

             st.erase(P(a[pre[x]], pre[x])), del(pre[x]);

         if (nxt[x] && nxt[x] != n + )

             st.erase(P(a[nxt[x]], nxt[x])), del(nxt[x]);

     }

     printf("%lld\n", ans);

 }

Luogu1484

Luogu 3620 数据备份 - Set

Solution

Code