夜深人静写题解系列??

 

题意:

现在有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;
}