三个点wa...TAT
(1)不要用一个数直接^1,最后得到的不一定是1/0
(2)走n步,是1->n+1
1->n,是走n-1步
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<cstdio> #include<cstdlib> #include<queue> #include<cstring> #include<algorithm> using namespace std; int n,m,sx,sy,k; const int N=203; char mp[N][N]; int f[N][N]; struct node { int v,pos; node(int vv,int pp) { v=vv,pos=pp; } node(){} }; int ans; deque <node> q; int py[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; void dp(int x,int y,int len,int fx) { q.clear() ; int mx=(fx<2 ?n :m); for(int stp=1;stp<=mx;stp++)//初始点走n-1到终点,走n就越界了... ... { if(mp[x][y]=='x') q.clear() ; else { int val=f[x][y],mxx=stp-len; if(!q.empty() && q.front() .pos < mxx ) q.pop_front() ; if(val!=-1) { while(!q.empty() && q.back() .v +stp -q.back() .pos <=val) q.pop_back() ; q.push_back(node(val,stp)); } if(!q.empty() ) f[x][y] =q.front() .v+stp -q.front() .pos, ans=max(ans,f[x][y]); } x+=py[fx][0],y+=py[fx][1]; } } int main() { scanf("%d%d%d%d%d ",&n,&m,&sx,&sy,&k); for(int i=1;i<=n;i++) scanf("%s ",mp[i]+1); memset(f,-1,sizeof(f)); f[sx][sy]=0; int l,r,fx; for(int i=1;i<=k;i++) { scanf("%d%d%d",&l,&r,&fx); if(fx<=2) for(int j=1;j<=m;j++) dp(n*(2-fx)+fx-1,j,r-l+1,fx-1);//直接写^1,返回的值不小啊 else for(int j=1;j<=n;j++) dp(j,m*(4-fx)+fx-3,r-l+1,fx-1); } printf("%d ",ans); return 0; }
再附上最大定长连续区间和,
区别一下写法:
int main() { scanf("%d%d",&n,&k); int pre=0,x; q.push_back(node(0,0)); for(int i=1;i<=n;i++) { scanf("%d",&x); pre+=x; //query int ll=i-k; while(!q.empty() && q.front() .pos <ll ) q.pop_front() ; if(!q.empty() ) ans=max(ans,pre-q.front() .sum); //output while(!q.empty() && q.back() .sum>=pre ) q.pop_back() ; q.push_back(node(pre,i)); } printf("%d ",ans);//不可以不选 return 0; }
瑰丽华尔兹:
if(!q.empty() && q.front() .pos < mxx ) q.pop_front() ; if(val!=-1) { while(!q.empty() && q.back() .v +stp -q.back() .pos <=val) q.pop_back() ; q.push_back(node(val,stp)); } if(!q.empty() ) f[x][y] =q.front() .v+stp -q.front() .pos, ans=max(ans,f[x][y]);
所以不同的题,不同写法呀