思维+建图
首先,万物起源:
对于这种两个变动的题目,我们相对的看
可以给金的每次移动向前增加一位
然后我们在草稿上画出一个金可以走到的所有格点
会发现,正好以斜线为界限的范围是这个金可以走到的地方
但是,还有一个问题,这里是一轮过后,即金和步都走一步后
但是还有可能步还没走就让金吞了
因此,为了避免这种情况下的漏算,我们不妨拆点,对于每一个点
我们拆一个点正好在他头上。
然后我们遍历,连边
对于拆的点,我们原来的点不和他连边
但是,这样有一个问题:
即,如果出现了两个原来的点他们正好连着,即点b在点a的头上
那么我们就尴尬了
为了解决这个问题
我们换统计点权为统计边权
我们事先排序,在此之后我们再判断是否存在这种情况
如果存在这种情况,我们让a->b,权值为1,且让之后所有的连向b的点权值都赋为2
否则,我们拆点
然后还有一个坑点,就是,如果初始时,我们有一个点正好在金的正下方
那么我们最终的答案还要加上
(但是在代码中,我是连接金和这个点了)
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int max_n = 10010; const int max_m = 1e7; struct edge { int to,cost,next; }E[max_m]; int head[max_n]; int cnt=1; void add(int from,int to,int cost) { E[cnt].to=to; E[cnt].cost=cost; E[cnt].next=head[from]; head[from]=cnt++; } ll xs[max_n],ys[max_n]; int tot=0; bool check(int i,int j) { return ys[j]>ys[i] && llabs(xs[j]-xs[i])<=llabs(ys[j]-ys[i]); } int used[max_n]; int dfs(int u) { if (used[u])return used[u]; int ans=0; for (int i=head[u];i;i=E[i].next) { int v = E[i].to; ans=max(ans,E[i].cost+dfs(v)); } return used[u]=ans; } int weights[max_n]; int help[max_n]; bool cmp(int a,int b) { return xs[a]==xs[b]?ys[a]<ys[b]:xs[a]<xs[b]; } int main() { ios::sync_with_stdio(0); int T;cin>>T; while (T--) { tot=1; cin>>xs[tot]>>ys[tot]; int n;cin>>n; for (int i=0;i<=n*2+100;++i)head[i]=used[i]=weights[i]=0,help[i]=i; cnt=1; for (int i=1;i<=n;++i) { ++tot; cin>>xs[tot]>>ys[tot]; } sort(help+2,help+2+n); for (int _=2;_<=n;++_) { int i = help[_]; int j = help[_+1]; if (xs[i]==xs[j] && ys[i]==ys[j]-1) { weights[j]=1; } else { ++tot; xs[tot]=xs[i]; ys[tot]=ys[i]+1; if (xs[tot]==xs[1] && ys[tot]==ys[1]) { add(1,tot,1); } } } for (int i=1;i<=tot;++i) { for (int j=1;j<=tot;++j) { if (llabs(ys[i]-ys[j])<=1 && xs[i]==xs[j])continue; if (check(i,j)) { add(i,j,1+weights[j]); } } } cout<<dfs(1)<<endl; } }