cf-edu165C

发表于 更新于 分类于 ， ， 阅读次数： 4 Waline： 本文字数： 875 阅读时长 ≈ 3 分钟

题意：

有一种操作：选择数组中的一个元素，并用其邻近元素的值替换它。求经过k次操作数组累和的最小值。

Problem - C - Codeforces

题解：

教育场的题，特别是c题总是相对简单（ps:也可能是因为少怪题和近期写的少了的缘故。）但是总是很有意义。考虑这一题。显然容易注意到k的数据范围是小于10的（可以暴搜:) 假的！），很容易想到用dp做法可以解。

但为什么不能采用别的解法呢？

考虑一种简单的贪心，即仅仅对最小值进行左右拓展。很容易证伪如k==1

2,1,1,2,5

显然这种情况对于第四个数字向右扩展是可行的而非对1进行操作。

注意到每次操作实际贡献的是相邻两个数字之间的差值，并且每次操作会改变三个数的相邻差值。不妨让我们试试差分与优先队列，我们将数组做两次差分，每次操作取其中最小值，这是可行的吗? 考虑这样一种情形，对于差分值有多个位置相同，我们应该修改哪一个位置使得差分数组的后续得修改操作能得到我们需要的最小值呢？显然，这样的操作需要更多信息而并非仅仅单纯的选择最小的差分值。

于是我们可以心安理得的考虑dp，状态表示简单表示如下：dpi,j表示前i个数字使用j次操作的最小值。

考虑状态转移，具体到我们的操作中来，注意到对于已经修改过的位置i再次进行操作是无意义的，这样的操作必然会导致不小于最优解，但在状态转移中取最小，可重，不漏。

[x,a,b,c,y] -> [x,x,x,x,y]->[x,x,y,y,y] 其中含有无意义的两步操作

再次注意k特别小的特性，于是我们想到枚举i的前k个元素，考虑这个区间中每个j的每个状态转移过来（由i扩展到j和由j扩展到i）的最小和。

下面是具体的转移方法，注意一下边界问题，读者也可以按自己的喜好来确定如何转移。

对于i，我们找到一个左边界ii，操作使得[ii+1,i]当中的数等于ak|k>ii&&k<=i，因此所需操作数为i-ii-1

最后注意一下答案不一定为操作k次。维护一下前缀和礼貌的减少一下时间复杂度。。。如果你想要更礼貌点，尝试与处理一下k长度内的最小值吧！但笔者比较懒，能ac干嘛优化：）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void slove() {
    cin>>n>>m;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)f[i][j] = LLINF;

    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) pre[i] = a[i] + pre[i-1];
    f[0][0] = 0;
    for(int i=1;i<=n;i++) {
        for(int ii=i-1;ii>=0 && i-ii-1 <= m;ii--) {
            int t = i-ii-1;
            for(int j=t;j<=m;j++) {
                for(int k=ii+1;k<=i;k++) {
                    f[i][j] = min(f[i][j],f[ii][j-t] + a[k] * (i-ii));
                    f[i][j] = min(f[i][j],f[ii][j-t] + a[k] * (i-ii));
                    // cout<<i<<' '<<j<<' '<< f[i][j]<<nline;
                }
            }
        }
    }

    int ans = LLINF;
    for(int i=0;i<=m;i++) ans = min(ans,f[n][i]);
    cout<<ans<<endl;
}