传送门
简单的线性dp" role="presentation" style="position: relative;">dpdp。
直接推一推就行了。
貌似三个状态会卡空间啊。。。
笔者分了两个阶段考虑状态转移。
代码：
#include<bits/stdc++.h>
#define N 5001
#define inf 0x3f3f3f3f
using namespace std;
char xxx;
int n,t,f[N][N],s[N],b[N],ans=0;
char yyy;
int main(){
memset(f,-inf,sizeof(f));
scanf("%d%d",&n,&t),f[0][0]=0;
for(int i=1;i<=n;++i)scanf("%d",&s[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
for(int i=1;i<=n;++i){
if(i>=t){
for(int j=1;j<t;++j){
if(f[i-1][j]!=-inf)f[i][j]=f[i-1][j]-s[i];
if(f[i-1][j-1]!=-inf)f[i][j]=max(f[i][j],f[i-1][j-1]+s[i]);
}
if(f[i-1][t-1]!=-inf)f[i][0]=f[i-1][t-1]+s[i]+b[i];
if(f[i-1][0]!=-inf)f[i][0]=max(f[i][0],f[i-1][0]-s[i]);
}
else{
for(int j=1;j<i;++j){
if(f[i-1][j]!=-inf)f[i][j]=f[i-1][j]-s[i];
if(f[i-1][j-1]!=-inf)f[i][j]=max(f[i][j],f[i-1][j-1]+s[i]);
}
f[i][i]=f[i-1][i-1]+s[i];
if(f[i-1][0]!=-inf)f[i][0]=f[i-1][0]-s[i];
}
for(int j=0;j<t;++j)ans=max(ans,f[i][j]);
}
cout<<ans;
return 0;
}