问题标题: 很简单的一题——1632

#include<iostream>
#include<cstring>
using namespace std;
int n,m,k,T,tj;
int x,y,v,mp[5005][5005],q[5005],h,t,mx=0,mxa[5005],ll,f[5005][5005];
void push(int ii,int e){
	while(h!=t&&e-q[h]>=k)h++;
	while(h!=t&&mp[ii][q[t-1]]<=mp[ii][e])t--;
	q[t++]=e;
}
int dfs(int xt,int yt){
	if(f[xt][yt])return f[xt][yt];
	if(xt>n)return 0;
	memset(mxa,0,sizeof(mxa));
	mx=0;
	memset(q,0,sizeof(q));
	for(int i=1;i<T*2+1;i++)push(xt,i);//处理第xt行 
	for(int i=T*2+1;i<=m;i++){
		push(xt,i);
		if(mp[xt][q[h]]>mx){
			mx=mp[xt][q[h]];
			ll=0;
			for(int j=max(i-T,0);j<=min(i+T,m);j++){
				ll++;
				mxa[ll]=j;
			}
		}
		else if(mp[xt][q[h]]==mx){
			for(int j=max(i-T,0);j<=min(i+T,m);j++){
				ll++;
				mxa[ll]=j;
			}
		} 
	}
	int as=0,yl=0,mxy[5005];
	for(int i=1;i<=ll;i++){//计算求值 
		if(mxa[i]<0||mxa[i]>m||mxa[i]<yt-T||mxa[i]>yt+T);
		else{
			if(as<dfs(xt+1,mxa[i])+mx){
				as=dfs(xt+1,mxa[i])+mx;
				yl=0;
				for(int j=i-T;j<=i+T;j++){
					yl++;
					mxy[yl]=j;
				}
			}
			else if(as==dfs(xt+1,mxa[i])+mx){
				for(int j=i-T;j<=i+T;j++){
					yl++;
					mxy[yl]=j;
				}
			} 
		}	
	}
	for(int i=1;i<=yl;i++)f[xt][mxy[i]]=as;
	return as;
}
int main(){
	cin>>n>>m>>k>>T;
	for(int i=1;i<=k;i++){
		cin>>x>>y>>v;
		mp[x][y]=v;
	}
	for(int i=1;i<T*2+1;i++)push(1,i);//先处理第1行 
	for(int i=T*2+1;i<=m;i++){
		push(1,i);
		if(mp[1][q[h]]>mx){
			mx=mp[1][q[h]];
			ll=0;
			for(int j=max(i-T,0);j<=min(i+T,m);j++){
				ll++;
				mxa[ll]=j;
			}
		}
		else if(mp[1][q[h]]==mx){
			for(int j=max(i-T,0);j<=min(i+T,m);j++){
				ll++;
				mxa[ll]=j;
			}
		} 
	}
	int ans=0;
	for(int i=1;i<=ll;i++){
		ans=max(ans,dfs(2,i)+mx);
	}
	cout<<ans;
	return 0;
}
//310
//030
//003

本弱鸡的WA0代码

1632   棋盘拿能量

思路：单调队列加记忆化搜索

速答！！！

包涵宇在2020-12-04 16:38:32追加了内容

顶