F1 & F2 Pictures with Kittens (easy and hard version) dp，单调队列

F1传送门
F2传送门

easy version 思路 （dp）：

设f[i][j]表示 遍历到了 第i 个数，并且选择了第i个数时选择的所有个数为j
因为我们选择了第i个，那么i的前面k个数必定有一个数 是被选择的
例如：1 2 3 4 5 6 7 k=2,假设我选择了6，那么4，5一定有一个会被选择。
这样的话 状态转移方程 则可以表示为：f[i][j] =max(f[i][j], f[i - h][j - 1] + a[i])
h 取值范围 为1-k ，用上面的例子来说就是可以用4转移，也可以用5转移，我们取max
我们还可以先把所有结果初始化为-inf，这样对于不可能的情况其值肯定比-1要小，我们再取max就行了

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long 
#define pii pair<int,int>
#define r0 return 0
const int N = 205;
map<int, int>mp;
vector<int>v;
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int st[N];
int g[N][N];
int a[N];
ll f[N][N];
int q[N];
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n,k,x;
	cin >> n>>k>>x;
	for (int i = 1; i <= n; i++) cin >> a[i];
	memset(f, -0x3f, sizeof f);
	f[0][0] = 0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=x&&j<=i;j++)
			for (int h = 1; h <= k && i-h>=0; h++)
			{
				f[i][j] =max(f[i][j], f[i - h][j - 1] + a[i]);
			}
	ll ans = -1;
	for (int i = n - k + 1; i <= n; i++)
		ans = max(ans, f[i][x]);
	cout << ans << endl;
	r0;
}

hard version 思路 （dp + 单调队列）：

上面的easy版本我们使用了三重循环，细看第三重循环，我们对一系列数取max 好像可以用单调队列优化？我们从当前选定的数即i开始往前面取数，如果已经用单调队列排序好了，那么直接取队头元素就可以了。有一点细节就是这里的 递减 顺序 是要按照f[i-1][j-1] 和 f[p[l][j-1]来比较，而不能按照a[i-1]和a[p[l]]来比较，因为我们初始化f[0][0]为0，f[1][0]等等都是-inf的,但是a[1] 会比a[0]大

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long 
#define pii pair<int,int>
#define r0 return 0
const int N = 5005;
map<int, int>mp;
vector<int>v;
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int st[N];
int g[N][N];
int a[N];
ll f[N][N];
int q[N];
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n,k,x;
	cin >> n>>k>>x;
	for (int i = 1; i <= n; i++) cin >> a[i];
	memset(f, -0x3f, sizeof f);
	f[0][0] = 0;
	for (int j = 1; j <= x; j++)
	{
		int l = 1, r = 0; //数组模拟队列
		for (int i = 1; i <= n; i++)
		{
			while (l <= r && q[l] < i - k) l++;
			while (l <= r && f[i - 1][j - 1] > f[q[r]][j - 1]) r--;
			q[++r] = i - 1;
			f[i][j] = f[q[l]][j - 1] + a[i];
		}
	}
	ll ans = -1;
	for (int i = n - k + 1; i <= n; i++)
		ans = max(ans, f[i][x]);
	cout << ans << endl;
	r0;
}