CF1389B Array Walk

CF传送门

题目大意：你前面一共有$n$个格子，每个格子都有它的分值$a_x$当你到达第$x$个格子就能获得第$x$个格子的得分$a_x$。初始时你站在第$1$个格子，每一次移动你可以选择向左或向右，特别地，向左移动的次数不能超过$z$。现在，请问你正好走了$k$步后，最大得分是多少

思路：一道基础的DP题
我们令$dp[i][j]$表示往左移动$i$步的基础上到达$j$个格子的最大得分
转移方程可得：$dp[i][j]=max(dp[i][j?1],dp[i?1][j+1])+a[j]$
显然当$j?1+i?2=k$时，$ans=max(ans,dp[i][j])$即为答案
最后注意一下边界即可

Code：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;int n,t,k,z,a[N],dp[10][N];int main(){
    scanf("%d",&t);while(t--){
    scanf("%d%d%d",&n,&k,&z);memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++) scanf("%d",&a[i]);int ans=0;for(int i=0;i<=z;i++){
    for(int j=1;j<=n;j++){
    dp[i][j]=dp[i][j-1]+a[j];if(i&&j!=n)dp[i][j]=max(dp[i][j],dp[i-1][j+1]+a[j]);if(j-1+i*2==k) ans=max(ans,dp[i][j]);}}printf("%d\n",ans);}return 0;
}