Teamwork G

理想分数100，实际分数100 题目描述 自认为是一道很简单的DP题目，考场上花了3min看题，5min想DP状态转移方程式，5min打出，0s过样例，5min构数据查错，一共二十分钟就过了这道题。感觉比第1题还水。

分析

一道很水的线性动态规划，设dp[i]表示前i个人最多能得到的技能水平之和，他对dp[min(i + k,n)]这个之前的有影响，而后面的又由后面k(j<=n)个的最大值得到，于是他就可以得到一个十分简单的状态转移方程$$f[j]=max(f[j],f[i]+sum\ast (j-i))$$当动态规划题目写出来了状态转移方程式，接下来还不简单吗？直接狂撸代码，反正代码量都只有这么小了。。。 先外层循环枚举结尾，循环0-n(1-n也行，就多在外面加个初始状态就可以了)。内层循环枚举后面会影响的从i到min(n,i + k)，一边存当前访问的最大值，一边更新当前的dp值，最后输出dp[n]，也就是1-n全部的技术值，时间复杂度$O(nk)$，也是快的飞起

code

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1e4 + 5; int n,k,a[MAXN],dp[MAXN]; int main() { freopen("worker.in","r",stdin); freopen("worker.out","w",stdout); scanf("%d %d",&n,&k); for(int i = 1;i <= n;i ++) scanf("%d",&a[i]); for(int i = 0;i <= n;i ++) { int maxx = 0; for(int j = i + 1;j <= min(i + k,n + 1);j ++) { maxx = max(maxx,a[j]); dp[j] = max(dp[j],dp[i] + maxx * (j - i)); } } printf("%d",dp[n]); return 0; }