https://codeforces.com/problemset/problem/1077/F1
这个其实是一个比较简单的dp了
题目大意：
给你n个数，让你从n个数里选出x个数，并且每隔k个至少选一个数。
开始不知道怎么去写，也不知道怎么去定义dp
这个应该是对于dp不是特别的熟练，实际上dp用途很广，而且可以用到的地方很多，效果也很好。
这种时候就应该大胆一点，你需要什么，想达成什么效果那就去这样定义。
这个题目，我们希望dp可以帮我们解决前面n个数，选了x个数的最大和，而且这个还必须每隔k就选择了一个数。
这个是大问题，子问题是什么呢？
如果我们选第i个数，那么前面n-1个数，选了x-1个数的最大和。。。。
否则就是我们不选第i个数，那么前面n-1个数，选了x个数的最大和。 ----这种情况我们最多可以向前面推k-1次
所以我们要怎么定义呢？
首先要有一维来记录到第几个数了，还有一维就是要记录我们选了多少个了，
两维记录可以唯一确定每一个状态，所以两维就够了
那到底怎么去定义这个dp呢？dp的含义是什么呢？
这个我觉得不是很好想。
dp[i][j]表示前面i个数，已经选了j个数的最大和吗？
但是因为这个有区间限制，就是每隔k就必须有一个数，所以这个时候我们就要确定前面的那个值的位置，
所以我们就定义为已经选择了第i个数，前面i个数 选了j个数的最大和。
状态定义好了之后，就是转移方程的确定了。
dp[i][j]=max(dp[i][j],dp[s][j-1]+a[i])
这个s其实就是i往前推，然后去最大值，所以需要三维。
而且这个往前推最多推k个数。
#include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <algorithm> #include <vector> #include <iostream> #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn = 1010; typedef long long ll; ll dp[2 * maxn][2 * maxn]; ll a[maxn];int main() {int n, k, x;scanf("%d%d%d", &n, &k, &x);for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);for(int i=0;i<=n;i++){for(int j=0;j<=x;j++){dp[i][j] = -inf;}}dp[0][0] = 0;for(int i=1;i<=n;i++){for(int j=1;j<=x;j++){for(int h=1;h<=k&&h<=i;h++){if (dp[i - h][j - 1] == -inf) continue;dp[i][j] = max(dp[i][j], dp[i - h][j - 1] + a[i]);// printf("dp[%d][%d]=%lld\n", i, j, dp[i][j]); }}}ll ans = -inf;for (int i = n - k + 1; i <= n; i++) ans = max(ans, dp[i][x]);if (ans < 0) printf("-1\n");else printf("%lld\n", ans);return 0; }
