题目描述
给定一行 n n n 个非负整数 a 1 ⋯ a n a_1 \cdots a_n a1⋯an。现在你可以选择其中若干个数,但不能有超过 k k k 个连续的数字被选择。你的任务是使得选出的数字的和最大。
输入格式
第一行两个整数 n n n, k k k。
以下 n n n 行,每行一个整数表示 a i a_i ai。
输出格式
输出一个值表示答案。
样例 #1
样例输入 #1
5 2
1
2
3
4
5
样例输出 #1
12
提示
对于 20 % 20\% 20% 的数据, n ≤ 10 n \le 10 n≤10。
对于另外 20 % 20\% 20% 的数据, k = 1 k=1 k=1。
对于 60 % 60\% 60% 的数据, n ≤ 1000 n \le 1000 n≤1000。
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 100000 1 \le n \le 100000 1≤n≤100000, 1 ≤ k ≤ n 1 \le k \le n 1≤k≤n, 0 ≤ 0 \le 0≤ 数字大小 ≤ 1 , 000 , 000 , 000 \le 1,000,000,000 ≤1,000,000,000。
时间限制 500 500 500 ms。
思路
将题意重新理解一下,将连续选数不超过
k
k
k 个抽象为每隔长度小于
k
k
k
的区间内选择一个数删掉,那么我们定义
f
i
f_i
fi 为删除数
a
i
a_i
ai 时删除数字之和的最小值,易得状态转移方程:
f i = { a i , i ≤ k m i n i − k + 1 i { f j } + a i , i > k f_i= \begin{cases} a_i \ ,\ i \le k \\ min_{i-k+1}^i \{f_j\}+a_i\ ,\ i>k\\ \end{cases} fi={ai , i≤kmini−k+1i{fj}+ai , i>k
最后答案即 ∑ 1 n a i − m i n n − k − 1 n { f i } \sum_1^n a_i -min_{n-k-1}^n \{f_i\} ∑1nai−minn−k−1n{fi}
很明显这是一个滑动窗口求区间最小值,因此我们使用单调队列来优化这个动态规划的实现。
代码
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define bit1(x) __builtin_popcount(x)
#define Pqueue priority_queue
#define lc p << 1
#define rc p << 1 | 1
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> PII;
const ll mod = 1000000007;
const ll N = 1e6 + 10;
const ld eps = 1e-9;
const ll inf = 1e18;
const ll P = 131;
const ll dir[8][2] = {1, 0, 0, 1, -1, 0, 0, -1, 1, 1, 1, -1, -1, 1, -1, -1};
void solve()
{
int n, k;
ll tot = 0;
cin >> n >> k;
vector<ll> f(n), a(n);
for (ll &i : a)
cin >> i, tot += i;
deque<ll> q;
for (int i = 0; i < n; i++)
{
if (i <= k)
f[i] = a[i];
else
f[i] = f[q.front()] + a[i];
if (!q.empty() && i - q.front() >= k + 1)
q.pop_front();
while (!q.empty() && f[q.back()] > f[i])
q.pop_back();
q.push_back(i);
}
cout << tot - *min_element(f.end() - k - 1, f.end());
}
int main()
{
IOS int T = 1;
// cin>>T;
while (T--)
solve();
return 0;
}
/*
oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
x o
o _/_/_/_/ _/ x
x _/ o
o _/_/_/_/ _/ _/_/ _/_/ _/_/_/ _/_/ _/_/_/ _/_/ _/_/_/ _/ _/ _/ x
x _/ _/_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ o
o _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/ x
x _/ _/ _/_/ _/ _/ _/ _/_/_/ _/_/ _/ _/ _/ _/ _/ o
o _/ _/ _/ x
x _/ _/_/ _/ o
o x
xo6xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
*/