题目

题目描述

给你$n$个数$a_1, a_2, … a_n$，你要从$1$到$n$选数，你最多有$k$次机会可以跳过一个数不选它，但是后面的数权值会$+ 1$，形式化的

如果你跳过了$a_i$，那么$a_{i + 1}, a_{i + 2}, a_n$都要$+ 1$

$+ 1$可以被累计，也就是一个位置可以被加多次

最小化选出的数的和，并输出

数据范围

$t$组数据， $1 \leq t \leq 100$

$1 \leq k \leq n \leq 2 \times 10 ^ 5, \sum n \leq 2 \times 10 ^ 5$

$1 \leq a_i \leq 10^9$

题解

dp

显然， $k$次机会一定要全用完，因为如果我们没有用完$k$次机会，那我们可以在当前状态从后往前找到第一个没被跳过的，把它跳过，答案一定会变小

我们尝试$dp$，那么对于一个位置$i$的数我们有选和不选两种状态，不选的话会对后续的数产生影响，消除影响的话需要记录$1 … i$位置跳过了多少个，所以我们设$dp[i][j]$表示选到第$i$个数，跳过了$j$个数的方案，那么有

$f[i][j] = min\{f[i - 1][j] + a[i], f[i - 1][j - 1] + n - i - j\}$

由于$n \leq 2 \times 10^5$，时空都无法接受

贪心

直觉告诉我们虽然跳过一个数有了后续的影响，但是$a_i$的大小肯定还是有主导的，应该可以贪心，先设这$n$个数的和为$sum$，初始$ans = sum$

观察可得，对答案有影响的除了$a_i$本身的大小，还有位置$i$，举个例子，如果$k$个跳过全都在最后，那么$+1$操作就相当于没有了。原因在于每个数的贡献除了$a_i$，还有$i$之后选的数的个数，那我们尝试算上位置的贡献

考虑单个数的贡献的话，我们不得不关注这个数后面还有几个被/没被跳过，这个过程无从下手；但是结果都是一样的： $k$个数被跳过了，所以我们尝试从结果反向推理，并且考虑整体的贡献

假设我们选出了$k$个位置的数用来跳过，其位置分别为$p_1, p_2, … , p_k$，那么会使答案减少$a_{p_1}, a_{p_2}, …, a_{p_k}$，同时增加$n - p_1 - (k - 1), n - p_2 -(k - 2), … , n - p_k$，增加的总贡献为$k \times n - \sum p - \frac{k(k - 1)}{2}$，最终一共会使答案减少$\sum (a_p + p) - k \times n + \frac{k(k - 1)}{2}$，式子中只有$p$是变量，那我们只要选择$a_i + i$最大的$k$个位置跳过就好了

通过反推和计算整体贡献的方法，我们成功消除了跳过的这些数位置之间的影响，转换成每个位置的贡献只与自己的位置有关

感觉这个方法很巧妙，不看题解我想不到

代码

#include <iostream>
#include <cstdio>
#include <algorithm>

int t;
int n, k;
int b[200005];
long long sum;

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        sum = 0;
        
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i ++)
        {
            int a;
            scanf("%d", &a);
            
            sum += a;
            b[i] = a + i;
        }
        
        std:: sort(b + 1, b + n + 1);
        std:: reverse(b + 1, b + n + 1);
        
        for(int i = 1; i <= k; i ++) sum -= b[i];
        sum += 1LL * k * n;
        sum -= 1LL * k * (k - 1) / 2;
        
        printf("%lld\n", sum);
    }
    
    return 0;
}

Zth's Blog

cf792d 贪心

题目

题目描述

数据范围

题解

dp

贪心

代码