PKU演習問メモ(8/2)
暑いし体だるいし頭動かないし眠れない。
No. | 問題名 | 問題の種類および解法 | 難易度 |
---|---|---|---|
1984 | Navigation Nightmare | Union-find | ★★★☆☆ |
2948 | Martian Mining | 動的計画法 | ★★☆☆☆ |
1984 Navigation Nightmare
問題概要
座標平面上にn個の牧場がある。
それらの位置の関係がm個、
"F1の(東西南北の方向)距離dのところにF2"あるという形式で与えられる。
このとき、次のようなクエリに答えよ。
- I個目までの位置関係の情報で、F1とF2のマンハッタン距離を求められるのならその距離を、不可能なら-1を返す
ただし、n,m≦40000かつ
クエリの数kはk≦10000を満たす。
解法
マンハッタン距離は、一度決まってしまえば後は変わらない。
したがって、最初に全ての牧場の座標を計算しておき、クエリを求めるときに、それらがI番目までで求まるかどうかだけを調べればよい。
それには、まず入力を全て読み込み、クエリをIの順にソートして、
union-findを使い関係が求まるかを決めながら答えを配列に書き、
配列を求められている答えの順にソートして出力すればよい。
実装量はやや多目。
ソースコード
int n,m,q; int f1[40000],f2[40000]; struct Q{ int f1,f2,I,id; bool operator<(const Q &r)const{ return I<r.I; } }; Q qin[10000]; pi ans[10000]; int north[40000],east[40000],west[40000],south[40000]; int nd[40000],ed[40000],wd[40000],sd[40000]; int X[40000],Y[40000],p[40000]; //union-find int root(int x) { if(p[x]==x)return x; return p[x]=root(p[x]); } void merge(int a,int b) { a=root(a); b=root(b); if(a!=b)p[b]=a; } void load(int &s,int t) { for(;s<t;s++)merge(f1[s],f2[s]); } int dist(int f1,int f2) { if(root(f1)!=root(f2))return -1; if(X[f1]==inf||X[f2]==inf||Y[f1]==inf||Y[f2]==inf)return -1; return abs(X[f1]-X[f2])+abs(Y[f1]-Y[f2]); } //coodinate calculating void dfs(int c) { int t; if(nd[c]!=-1&&X[t=north[c]]==inf)X[t]=X[c],Y[t]=Y[c]+nd[c],dfs(t); if(sd[c]!=-1&&X[t=south[c]]==inf)X[t]=X[c],Y[t]=Y[c]-sd[c],dfs(t); if(ed[c]!=-1&&X[t=east[c]]==inf)X[t]=X[c]+ed[c],Y[t]=Y[c],dfs(t); if(wd[c]!=-1&&X[t=west[c]]==inf)X[t]=X[c]-wd[c],Y[t]=Y[c],dfs(t); } int main() { scanf("%d%d",&n,&m); rep(i,n)nd[i]=ed[i]=wd[i]=sd[i]=-1; rep(i,m){ int a,b,d; char c; scanf("%d%d%d %c",&a,&b,&d,&c); f1[i]=--a; f2[i]=--b; if(c=='N')north[a]=b,south[b]=a,nd[a]=sd[b]=d; else if(c=='S')north[b]=a,south[a]=b,sd[a]=nd[b]=d; else if(c=='E')east[a]=b,west[b]=a,ed[a]=wd[b]=d; else east[b]=a,west[a]=b,wd[a]=ed[b]=d; } rep(i,n)X[i]=Y[i]=inf,p[i]=i; rep(i,n)if(X[i]==inf)X[i]=Y[i]=0,dfs(i); scanf("%d",&q); rep(i,q){ int a,b; scanf("%d%d%d",&a,&b,&qin[i].I),qin[i].id=i; qin[i].f1=a-1; qin[i].f2=b-1; } sort(qin,qin+q); int cur=0; rep(i,q) { if(cur<qin[i].I)load(cur,qin[i].I); ans[i]=mp(qin[i].id,dist(qin[i].f1,qin[i].f2)); } sort(ans,ans+q); rep(i,q)printf("%d\n",ans[i].second); return 0; }
2948 Martian Mining
問題概要
nxmマスのグリッド上に2種類の金属yeyeniumとblogiumが分布しており、それをベルトコンベアを使って回収したい。
ベルトコンベアの向きは上向きまたは左向きのみであり、ベルトコンベアは同方向同士のものを連結することができる。
blogiumの回収基地はグリッド上部、yeyeniumの回収基地はグリッド左部である。
2種類の金属の分布が与えられたとき、回収できる金属の量の和の最大値を求めよ。
n,m≦500を満たす。
解法
動的計画法(メモ化再帰)による。
範囲(0,0)から(w,h)までの最適解は、
- その長方形の右側に上へのベルトコンベアを作る
- その長方形の下側に左へのベルトコンベアを作る
のいずれかになる。
それぞれの場合について、y,xを1減らして再帰が可能なため、それをコードにすればよい。
ソースコード
int h,w; int blog[500][500],yeye[500][500]; int dp[501][501]; int rec(int y,int x) { if(y<=0||x<=0)return 0; if(dp[y][x]!=-1)return dp[y][x]; int bottom=0,right=0,ret=0; rep(i,x)bottom+=yeye[y-1][i]; rep(i,y)right+=blog[i][x-1]; ret=max(rec(y-1,x)+bottom,rec(y,x-1)+right); return dp[y][x]=ret; } int main() { while(scanf("%d%d",&h,&w),h){ rep(i,h)rep(j,w)scanf("%d",yeye[i]+j); rep(i,h)rep(j,w)scanf("%d",blog[i]+j); rep(i,h+1)fill_n(dp[i],w+1,-1); printf("%d\n",rec(h,w)); } return 0; }