[BZOJ4200][Noi2015]小园丁与老司机

4200: [Noi2015]小园丁与老司机

Time Limit: 20 Sec  Memory Limit: 512 MBSec  Special Judge
Submit: 106  Solved: 58
[Submit][Status][Discuss]

Description

小园丁 Mr. S 负责看管一片田野,田野可以看作一个二维平面。田野上有 nn 棵许愿树,编号 1,2,3,…,n1,2,3,…,n,每棵树可以看作平面上的一个点,其中第 ii 棵树 (1≤i≤n1≤i≤n) 位于坐标 (xi,yi)(xi,yi)。任意两棵树的坐标均不相同。
老司机 Mr. P 从原点 (0,0)(0,0) 驾车出发,进行若干轮行动。每一轮,Mr. P 首先选择任意一个满足以下条件的方向:
为左、右、上、左上 45∘45∘ 、右上 45∘45∘ 五个方向之一。
沿此方向前进可以到达一棵他尚未许愿过的树。
完成选择后,Mr. P 沿该方向直线前进,必须到达该方向上距离最近的尚未许愿的树,在树下许愿并继续下一轮行动。如果没有满足条件的方向可供选择,则停止行动。他会采取最优策略,在尽可能多的树下许愿。若最优策略不唯一,可以选择任意一种。
不幸的是,小园丁 Mr. S 发现由于田野土质松软,老司机 Mr. P 的小汽车在每轮行进过程中,都会在田野上留下一条车辙印,一条车辙印可看作以两棵树(或原点和一棵树)为端点的一条线段。
在 Mr. P 之后,还有很多许愿者计划驾车来田野许愿,这些许愿者都会像 Mr. P 一样任选一种最优策略行动。Mr. S 认为非左右方向(即上、左上 45∘45∘ 、右上 45∘45∘ 三个方向)的车辙印很不美观,为了维护田野的形象,他打算租用一些轧路机,在这群许愿者到来之前夯实所有“可能留下非左右方向车辙印”的地面。
“可能留下非左右方向车辙印”的地面应当是田野上的若干条线段,其中每条线段都包含在某一种最优策略的行进路线中。每台轧路机都采取满足以下三个条件的工作模式:
从原点或任意一棵树出发。
只能向上、左上 45∘45∘ 、右上 45∘45∘ 三个方向之一移动,并且只能在树下改变方向或停止。
只能经过“可能留下非左右方向车辙印”的地面,但是同一块地面可以被多台轧路机经过。
现在 Mr. P 和 Mr. S 分别向你提出了一个问题:
请给 Mr .P 指出任意一条最优路线。
请告诉 Mr. S 最少需要租用多少台轧路机。
 

Input

 输入文件的第 1 行包含 1 个正整数 n,表示许愿树的数量。

接下来 n 行,第 i+1 行包含 2个整数 xi,yi,中间用单个空格隔开,表示第 i 棵许愿树的坐标。
 

Output

输出文件包括 3 行。
输出文件的第 1 行输出 1 个整数 m,表示 Mr. P 最多能在多少棵树下许愿。
输出文件的第 2 行输出 m 个整数,相邻整数之间用单个空格隔开,表示 Mr. P 应该依次在哪些树下许愿。
输出文件的第 3 行输出 1 个整数,表示 Mr. S 最少需要租用多少台轧路机。
 

Sample Input

6
-1 1
1 1
-2 2
0 8
0 9
0 10

Sample Output

3
2 1 3
3

explanation

最优路线 2 条可许愿 3 次:(0,0)→(1,1)→(−1,1)→(−2,2)(0,0)→(1,1)→(−1,1)→(−2,2) 或 (0,0)→(0,8)→(0,9)→(0,10)(0,0)→(0,8)→(0,9)→(0,10)。 至少 3 台轧路机,路线是 (0,0)→(1,1)(0,0)→(1,1),(−1,1)→(−2,2)(−1,1)→(−2,2) 和 (0,0)→(0,8)→(0,9)→(0,10)(0,0)→(0,8)→(0,9)→(0,10)。

HINT


Source

 
[Submit][Status][Discuss]


HOME Back

第一问按Y排序,map记录每个向上、左、右方向最近的点,对于y坐标相同的点按x排序,如果$x_i>x_j$,一定是从j走到最左在走回i,如果$x_i<x_j$,一定是从j走到最走在走回i。维护一个单调栈即可。

第二问只需要在DP的同时记录决策点,输出路径。

第三问相当于判断每条边是否可以存在于最长路中,然后下界为1跑最小流。如果判断每条边可以倒着DP一遍考虑是否两端和等于ans。注意,倒着DP和正着DP会有差别。

  1 #include<map>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define N 50050
  6 #define S (n+1)
  7 #define T (n+2)
  8 #define SS (n+3)
  9 #define TT (n+4)
 10 using namespace std;
 11 struct dp{int x,y,id,f,from;bool f1,f2;}a[N],b[N];
 12 int n,f[N],g[N],X[N],Y[N];
 13 int head[N],tot,d[N];
 14 struct edge{int next,to,v;}e[2100000];
 15 inline void add(int u,int v,int w)
 16 {
 17     e[tot]=(edge){head[u],v,w};
 18     head[u]=tot++;
 19     e[tot]=(edge){head[v],u,0};
 20     head[v]=tot++;
 21 }
 22 int SAP(int start,int end,int n)
 23 {
 24     int u,neck,tmp,i,flow_ans=0,cur_flow;
 25     int numh[N],d[N],cure[N],pre[N];
 26     memset(d,0,sizeof(d));
 27     memset(numh,0,sizeof(numh));
 28     memset(pre,-1,sizeof(pre));
 29     for(int i=0;i<=n;i++)
 30     cure[i]=head[i];
 31     numh[0]=n;
 32     u=start;
 33     while(d[start]<n)
 34     {
 35         if(u==end)
 36         {
 37             cur_flow=1e9;
 38             for(i=start;i!=end;i=e[cure[i]].to)
 39             if(cur_flow>e[cure[i]].v)
 40             neck=i,cur_flow=e[cure[i]].v;
 41             for(i=start;i!=end;i=e[cure[i]].to)
 42             {
 43                 tmp=cure[i];
 44                 e[tmp].v-=cur_flow;
 45                 e[tmp^1].v+=cur_flow;
 46             }
 47             flow_ans+=cur_flow;
 48             u=neck;
 49         }
 50         for(i=cure[u];i!=-1;i=e[i].next)
 51         if(e[i].v&&d[u]==d[e[i].to]+1)break;
 52         if(i!=-1)
 53         {
 54             cure[u]=i;
 55             pre[e[i].to]=u;
 56             u=e[i].to;
 57         }
 58         else
 59         {
 60             if(--numh[d[u]]==0)break;
 61             cure[u]=head[u];
 62             for(tmp=n,i=head[u];i!=-1;i=e[i].next)
 63             if(e[i].v)tmp=min(tmp,d[e[i].to]);
 64             d[u]=tmp+1;
 65             numh[d[u]]++;
 66             if(u!=start)u=pre[u];
 67         }
 68     }
 69     return flow_ans;
 70 }
 71 bool operator<(dp x,dp y)
 72 {
 73     if(x.y!=y.y)return x.y<y.y;
 74     return x.x<y.x;
 75 }
 76 inline void update(int i,int j)
 77 {
 78     if(a[i].f<a[j].f+1)
 79     a[i].f=a[j].f+1,a[i].from=j,a[i].f1=0;
 80 }
 81 void print(int x,bool f)
 82 {
 83     if(x==n+1)return;
 84     if(!f)print(a[x].from,a[x].f1);
 85     else print(b[x].from,0);
 86     if(!a[x].f1||f)
 87     printf("%d ",a[x].id);
 88     else if(!a[x].f2)
 89     {
 90         for(int i=a[x].from-1;a[i].y==a[x].y;i--)
 91         printf("%d ",a[i].id);
 92         for(int i=a[x].from+1;i<=x;i++)
 93         printf("%d ",a[i].id);
 94     }
 95     else
 96     {
 97         for(int i=a[x].from+1;a[i].y==a[x].y;i++)
 98         printf("%d ",a[i].id);
 99         for(int i=a[x].from-1;i>=x;i--)
100         printf("%d ",a[i].id);
101     }
102 }
103 map<int,int>L,R,U;
104 void solve(int ans)
105 {
106     memset(head,-1,sizeof(head));
107     L.clear();
108     R.clear();
109     U.clear();
110     for(int i=1;i<=n;i++)
111     X[i]=a[n+1-i].x,Y[i]=a[n+1-i].y;
112     X[n+1]=Y[n+1]=0;
113     for(int i=1;i<=n;i++)f[i]=1;
114     for(int l=1,r,x;l<=n+1;l=r+1)
115     {
116         for(r=l;r<=n&&Y[r+1]==Y[r];r++);
117         for(int i=l;i<=r;i++)
118         {
119             x=U[X[i]];
120             if(x)
121             {
122                 f[i]=max(f[i],f[x]+1);
123                 if((a[n+1-i].f||i==n+1)&&a[n+1-i].f+f[x]==ans)
124                 {
125                     add(n+1-x,n+1-i,1e9);
126                     d[n+1-x]--;d[n+1-i]++;
127                 }
128             }
129             x=L[X[i]+Y[i]];
130             if(x)
131             {
132                 f[i]=max(f[i],f[x]+1);
133                 if((a[n+1-i].f||i==n+1)&&a[n+1-i].f+f[x]==ans)
134                 {
135                     add(n+1-x,n+1-i,1e9);
136                     d[n+1-x]--;d[n+1-i]++;
137                 }
138             }
139             x=R[X[i]-Y[i]];
140             if(x)
141             {
142                 f[i]=max(f[i],f[x]+1);
143                 if((a[n+1-i].f||i==n+1)&&a[n+1-i].f+f[x]==ans)
144                 {
145                     add(n+1-x,n+1-i,1e9);
146                     d[n+1-x]--;d[n+1-i]++;
147                 }
148             }
149             U[X[i]]=i;
150             L[X[i]+Y[i]]=i;
151             R[X[i]-Y[i]]=i;
152         }
153         for(int i=l;i<=r;i++)g[i]=f[i];
154         int maxid=0;
155         for(int i=l+1;i<=r;i++)
156         {
157             if(!maxid||g[i-1]+(r-i+1)>g[maxid]+(r-maxid))maxid=i-1;
158             if(f[i]<g[maxid]+(r-maxid))
159             f[i]=g[maxid]+(r-maxid);
160         }
161         maxid=0;
162         for(int i=r-1;i>=l;i--)
163         {
164             if(!maxid||g[i+1]+(i+1-l)>g[maxid]+(maxid-l))maxid=i+1;
165             if(f[i]<g[maxid]+(maxid-l))
166             f[i]=g[maxid]+(maxid-l);
167         }
168     }
169     for(int i=0;i<=n;i++)
170     add(S,i,1e9),add(i,T,1e9);
171     for(int i=0;i<=n;i++)
172     if(d[i]>0)add(SS,i,d[i]);
173     else add(i,TT,-d[i]);
174     SAP(SS,TT,TT+1);
175     add(T,S,1e9);
176     SAP(SS,TT,TT+1);
177     printf("%d
",e[tot-1].v);
178 }
179 int main()
180 {
181     scanf("%d",&n);
182     for(int i=1;i<=n;i++)
183     scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i;
184     sort(a+1,a+n+1);
185     U[0]=L[0]=R[0]=n+1;
186     for(int l=1,r,x;l<=n;l=r+1)
187     {
188         for(r=l;r<n&&a[r+1].y==a[r].y;r++);
189         for(int i=l;i<=r;i++)
190         {
191             x=U[a[i].x];
192             if(x)update(i,x);
193             x=L[a[i].x+a[i].y];
194             if(x)update(i,x);
195             x=R[a[i].x-a[i].y];
196             if(x)update(i,x);
197         }
198         for(int i=l;i<=r;i++)b[i]=a[i];
199         int maxid=0;
200         for(int i=l+1;i<=r;i++)
201         {
202             if(b[i-1].f>b[maxid].f)maxid=i-1;
203             if(maxid&&a[i].f<b[maxid].f+(i-l))
204             {
205                 a[i].f=b[maxid].f+(i-l);
206                 a[i].f1=1;a[i].f2=0;a[i].from=maxid;
207             }
208         }
209         maxid=0;
210         for(int i=r-1;i>=l;i--)
211         {
212             if(b[i+1].f>b[maxid].f)maxid=i+1;
213             if(maxid&&a[i].f<b[maxid].f+(r-i))
214             {
215                 a[i].f=b[maxid].f+(r-i);
216                 a[i].f1=1;a[i].f2=1;a[i].from=maxid;
217             }
218         }
219         for(int i=l;i<=r;i++)
220         if(a[i].f)
221         {
222             U[a[i].x]=i;
223             L[a[i].x+a[i].y]=i;
224             R[a[i].x-a[i].y]=i;
225         }
226     }
227     int ans=0,id=n+1;
228     for(int i=1;i<=n;i++)
229     if(a[i].f>ans)
230     ans=a[i].f,id=i;
231     printf("%d
",ans);
232     print(id,0);puts("");
233     solve(ans);
234 }
View Code
原文地址:https://www.cnblogs.com/xuruifan/p/5577377.html