原题链接
题意：给你一个长为n的序列，以及一个代价公式， 然后求最大的代价: ∑i=lrai−k⌈r−l+1m⌉∑i=lrai−k⌈r−l+1m⌉,一般子序列cost问题肯定会想到dp，那么就要用dp来表示什么状态这道题结合了最大连续子序列和，以及长度对序列cost的影响由于有长度的影响所以要记录的状态信息就不只是当前位置dp[i][j]，i为当前位置，j为 除余大小 ；同时dp[i][1]~dp[i][m]也包含了该处所有的子序列长度状态 我们主要考虑在临近的转态转移下会因长度减去k的问题 要多减一个k： j=1,意味着就是要么取当前1个或者是其前一个i-1且状态为m时转移过来 不减k时 : j>1时，意味着就是其他中间状态就是从i-1, j-1状态直接来的
完整代码：
#include <cstdio> #include <iostream> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f ; const int N = 3e5 + 5; ll a[N]; //ll sum[N]; ll dp[N][20]; int main() { int n, m, k; cin >> n >> m >> k; a[0] = 0; for (int i = 1; i <= m; i ++)dp[0][i] = -inf; ll ans = 0; for (int i = 1; i <= n; i ++){ cin>>a[i]; for (int j = 1; j <= m; j ++){ if (j == 1)dp[i][j] = max(a[i] - k, dp[i - 1][m] + a[i] - k); else dp[i][j] = dp[i - 1][j - 1] + a[i]; ans = max(ans, dp[i][j]); } } cout<<ans<<endl; return 0; }
转载于:https://www.cnblogs.com/Tianwell/p/11276956.html
