题目描述
You are given an integer array a of length n.
You can perform the following operation: choose an element of the array and replace it with any of its neighbor’s value.
For example, if a=[3,1,2], you can get one of the arrays [3,3,2], [3,2,2] and [1,1,2] using one operation, but not [2,1,2] or [3,4,2].
Your task is to calculate the minimum possible total sum of the array if you can perform the aforementioned operation at most k times.
Input
The first line contains a single integer t (1≤t≤104) — the number of test cases.
The first line of each test case contains two integers n and k (1≤n≤3⋅105
; 0≤k≤10).
The second line contains n integers a1,a2,…,an (1≤ai≤109).
Additional constraint on the input: the sum of n over all test cases doesn’t exceed 3⋅105.
Output
For each test case, print a single integer — the minimum possible total sum of the array if you can perform the aforementioned operation at most k times.
样例
inputCopy
4
3 1
3 1 2
1 3
5
4 2
2 2 1 3
6 3
4 1 2 2 4 3
outputCopy
4
5
5
10
思路
一开始也没看出来是dp 补题的时候才看懂
由于k<10 , n<31e5 所以时间复杂度可以到O(nk) 百万级
暴力做法:每个位置都考虑做不做操、并做几次,时间复杂度o(n的看次方) 必爆
dp
状态表示:f(i, j) 对前i个数,做j次操作,和的最小值
状态计算f[i,j] =
1.操作j次但对第i个数不做操作 f[i, j] = f[i-1, j] + a[i];
2.操作j次并且对第i个数做操作 最多在第i个数的左边进行j次操作,并决定每次操作是否要更新最小值
算法1
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 300010;
typedef long long ll;
int n, k, t;
int a[N];
ll f[N][11];
void solve()
{
cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++)
{
for(int j = 0; j<=k; j++)
{
f[i][j] = f[i-1][j] + a[i];
ll mi = a[i];
for(int x = 0; x <=j && i-x-1>=0 ; x++)
{
f[i][j] = min(f[i][j], f[i-x-1][j-x] + (x+1)*mi);
mi = min(mi, (ll)a[i-x-1]);
}
}
}
cout << f[n][k]<<endl;
}
int main()
{
cin >> t;
while(t--) solve();
return 0;
}