P3800 Power收集

暴力 \(DP\) ， \(O(N\times M \times T)\) 。

#include<bits/stdc++.h>
using namespace std;
int N,M,K,T,ans;
int a[4001][4001];
int f[4001][4001];
int main()
{
	cin>>N>>M>>K>>T;
	for(int i=1,x,y,z; i<=K; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=z;
	}
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=M; j++)
		{
			for(int k=max(1,j-T); k<=min(M,j+T); k++){
				f[i][j]=max(f[i][j],f[i-1][k]);
			}
			f[i][j]+=a[i][j];
			if(i==N)
			{
				ans=max(ans,f[i][j]);
			}
		}
	}
	cout<<ans<<endl;
}

单调队列优化 \(O(N \times M)\) ，用滑动窗口来代替枚举 \(k\) 。

#include<bits/stdc++.h>
using namespace std;
int N,M,K,T,ans;
int a[4001][4001];
int que[4001];
int f[4001][4001];
int main()
{
	cin>>N>>M>>K>>T;
	for(int i=1,x,y,z; i<=K; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		f[x][y]=z;
	}
	for(int i=2; i<=N; i++)
	{
		static int head,tail,k;
		head=1;tail=0;k=1;
		for(int j=1; j<=M; j++)
		{
			while(k<=M&&k<=j+T)
			{
				while(head<=tail&&f[i-1][que[tail]]<=f[i-1][k])tail--;
				que[++tail]=k++;
			}
			while(que[head]<j-T)head++;
			f[i][j]+=f[i-1][que[head]];
			if(i==N)
			{
				ans=max(ans,f[i][j]);
			}
		}
	}
	cout<<ans<<endl;
}