生吃人，我很抱歉
by Astk @ 2020-09-02 17:26:18
已改过
代码
```
#include"iostream"
#include"cstdio"
#include"cmath"
#include"cstring"
using namespace std;
#define read(x) scanf("%d",&x)
int n,m,t,k;
int a[4005][4005];
int l,r,v;
int dp[4005][4005];
int q[4005],loc[4005],head=0,tail=1;
int ans=0;
int main()
{
read(n),read(m),read(k),read(t);
//cout<<n<<" "<<m<<endl;
for(int i=1;i<=k;i++)
{
read(l),read(r),read(v);
a[l][r]=v;
}
for(int i=1;i<=m;i++) dp[1][i]=a[1][i];
if(m<=t+1)
{
int ans=0;
for(int i=1;i<=n;i++)
{
int now=0;
for(int j=1;j<=m;j++) now=max(now,a[i][j]);
ans+=now;
}
printf("%d\n",ans);
return 0;
}
for(int i=2;i<=n;i++)
{
memset(q,0,sizeof(q)),memset(loc,0,sizeof(loc));
head=0,tail=1;
for(int j=1;j<=m+t;j++)
{
//cout<<i<<" "<<j<<endl;
while(j<=m&&head>=tail&&q[head]<=dp[i-1][j]) head--;
q[++head]=dp[i-1][j],loc[head]=j;
if(loc[tail]<j-2*t) tail++;
if(j>=t+1) dp[i][j-t]=q[tail]+a[i][j-t];
}
// for(int j=1;j<=t;j++)
// {
// if(q[tail]<m-t-t+j) tail++;
// dp[i][m-t+j]=q[tail]+a[i][m-t+j];
// }
}
for(int i=1;i<=m;i++) ans=max(ans,dp[n][i]);
printf("%d\n",ans);
return 0;
}
```
by Astk @ 2020-09-02 17:48:12
你下面那一坨我没看懂，上面我给你改了改，你自己理解一下，下面我杠掉了
by Astk @ 2020-09-02 17:48:44
@[hanzhongtlx](/user/184500)
by Astk @ 2020-09-02 17:51:25
@[Astk](/user/248895) 谢谢
by hanzhongtlx @ 2020-09-03 12:29:49