夜深人静写题解系列？？

 

题意：

现在有nn个柱子排在一起，每个柱子有个高度hi,0≤hi≤109hi,0≤hi≤109。
现在有至多kk次机会任意修改某些柱子的高度。
之后会执行操作：每次可以横向消去一段连续的柱子。问最终最少的操作次数是多少。

题解：

首先，对于之后执行的操作：

对于这种做法其实是有最优解的公式：

我们令序列为  ，并且

那么最小操作次数即为：

证明可以用差分数组详细证明，这里不再阐述

 

1.我们每当改变一个数的值，即改变某个柱子的高度的时候，我们假设令 改变的高度，那么最好让 ,这样根据上述公式差值会最小。

2.这时候思路就快接近正解了，可以设想如果使得，那么相当于把 删除

3.这时候最重要的一步来辽！题目转换成为：删除多少个柱子可以使得之后的执行操作次数最小？ 进一步转换：我们留下多少个柱子可以使得之后执行的操作次数最小？

4.毫无疑问，需要用到动态规划了，dp选手上线

设dp[i][k] 为 前i个柱子，保留k个可以产生的最小值，则:

这个方程比较好理解，前j个保留k-1个加上当前这个即保留了 k个。

由这个方程进行 for循环遍历dp

需要注意的几点：

1.边界问题，dp[0][0]=0， 0个保留0个就是0，其余赋值为INF，考虑到 dp[j][k-1]可以取到dp[0][k-1] 所以只能将dp[0][0]设为0

2.最后判断时，如果n==m 输出 0即可；

AC：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e7+5+5e6;
using namespace std;
const ll INF=1e15+7;
const ll mod=998244353;
ll n,m,p;
ll dp[305][305];
ll num[maxn];
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    for(int i=0;i<=n;i++)
        for(int k=0;k<=n;k++) dp[i][k]=INF;
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int k=1;k<=n-m;k++)
        {
            for(int j=0;j<i;j++)
            {
                dp[i][k]=min(dp[i][k],dp[j][k-1]+max(0ll,num[i]-num[j]));
            }
        }
    }
    //
    ll res=INF;
    for(int i=1;i<=n;i++)
        res=min(res,dp[i][n-m]);
    if(m==n) printf("0\n");
    else
        printf("%lld\n",res);
    return 0;
}