自动搬运

查看原文

来自洛谷，原作者为

	Dispwnl **

搬运于2025-08-24 21:33:08，当前版本为作者最后更新于2017-10-22 17:23:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

用二维数组

i存跳到第几步

j存跳到次数

若跳 f[i][j]=f[i-1][j-1]+s[i]

若不跳

f[i][j]=f[i-1][j]

当跳的次数是t的倍数时

若不跳

f[i][j]=f[i-1][j]-s[i]

若跳 f[i-1][j-1]+s[i]+b[i])

取最大值

初始化

f[i][0]=f[i-1][0]-s[i]

即一直不跳

输出f[n]i中最大值

# include<iostream>
# include<cstdio>
# include<cstring>
using namespace std;
int n,t;
int s[5001],b[5001];
int f[5001][5001];
int main()
{
    cin>>n>>t;
    for(int i=1;i<=n;i++)
      cin>>s[i];
    for(int i=1;i<=n;i++)
      cin>>b[i];
    for(int i=1;i<=n;i++)
      f[i][0]=f[i-1][0]-s[i];
    for(int i=1;i<=n;i++)
      for(int j=1;j<=i;j++)
         {
             f[i][j]=max(f[i-1][j]-s[i],f[i-1][j-1]+s[i]);
             if(j%t==0) f[i][j]=max(f[i-1][j]-s[i],f[i-1][j-1]+s[i]+b[i]);
         }
    int ans=0;
    for(int i=1;i<=n;i++)
      ans=max(ans,f[n][i]);
    cout<<ans;
    return 0;
}