这道题 网上题解还是很多很好的 强烈推荐黄学长 码风真的好看 神犇传送门 学习学习 算是道单调队列优化dp的裸题吧
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int M=205,inf=0x3f3f3f3f; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int n,m,sx,sy,k,ans; int head,tail,now; char a[M][M]; int f[M][M][M],q[M],pos[M]; int xi[5]={0,-1,1,0,0},yi[5]={0,0,0,-1,1}; bool pd(int x,int y){return (x>=1&&x<=n&&y>=1&&y<=m);} void push_ans(int now,int w){ if(w==-inf) return ; while(head<=tail&&q[tail]<w-now) tail--; q[++tail]=w-now; pos[tail]=now; } void dp(int i,int x,int y,int d,int l){ head=1; tail=0; int now=1; while(pd(x,y)){ if(a[x][y]=='x') head=1,tail=0; else push_ans(now,f[i-1][x][y]); while(head<=tail&&now-pos[head]>l) head++; if(head<=tail) f[i][x][y]=q[head]+now; else f[i][x][y]=-inf; ans=max(ans,f[i][x][y]); x+=xi[d]; y+=yi[d]; now++; } } int main() { int x,y,d,L; n=read(); m=read(); sx=read(); sy=read(); k=read(); for(int i=1;i<=n;i++) scanf("%s",a[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[0][i][j]=-inf; f[0][sx][sy]=0; for(int i=1;i<=k;i++){ x=read(); y=read(); d=read(); L=y-x+1; if(d==1) for(int j=1;j<=m;j++) dp(i,n,j,d,L); if(d==2) for(int j=1;j<=m;j++) dp(i,1,j,d,L); if(d==3) for(int j=1;j<=n;j++) dp(i,j,m,d,L); if(d==4) for(int j=1;j<=n;j++) dp(i,j,1,d,L); } printf("%d ",ans); return 0; }