Main » 2013 October 11 » [NOIP2010模拟赛]打鼹鼠
2:03 PM [NOIP2010模拟赛]打鼹鼠 |
这题想了一会就想出来了其实可以在n^2上做一些优化方程:f[i]=min(f[j]+1)(j<i)(time[j]>=time[i]+dis(p[i],p[j]))#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define M 100001 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int x[M],y[M],t[M],a[M],f[M],n,m; int dis(int i,int j) { return fabs(x[i]-x[j])+fabs(y[i]-y[j]); } int main() { cin>>n>>m; int i,j; FOR(i,1,m) { scanf("%d%d%d",&t[i],&x[i],&y[i]); } FOR(i,1,m) { f[i]=1; ROF(j,i-1,1) { if (t[i]-t[j]>=n*2) {f[i]=max(f[i],a[j]+1);break;} if (t[i]>=t[j]+dis(i,j)) f[i]=max(f[i],f[j]+1); } a[i]=max(a[i-1],f[i]); } printf("%d\n",a[m]); } |
|
|
| Total comments: 0 | |