每日一题Mar27th 数学考试
题目链接
涉及算法:动态规划
不妨设,表示以为第二个区间开头的,最大可以获得的分数值。
于是有转移方程,
观察中的部分,实际是要求在范围内的最大的,直接在转移过程中更新即可。单组数据的时间复杂度为,于是整体的时间复杂度为,可以通过本题。
代码:没什么可说的,边界注意一下即可
#include <bits/stdc++.h> #define int long long using namespace std; int f[400001],sum[400001],a[400001]; signed main (){ int T; ios::sync_with_stdio(false); cin >> T; while(T--){ memset(f, 0, sizeof(f)); memset(sum, 0, sizeof(sum)); memset(a, 0, sizeof(a)); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = n; i >= 1; i--) sum[i] = sum[i + 1] - a[i + k] + a[i];//倒序处理出sum[] int Max = sum[1]; for (int i = k + 1; i + k - 1 <= n; i++) f[i] = Max + sum[i], Max = max(Max, sum[i - k + 1]); Max = f[k + 1]; for (int i = k + 2; i + k - 1 <= n; i++) Max = max(Max, f[i]); cout << Max << endl; } return 0; }