NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 H.光輪2005

作者 主題: NPSC 2005 高中組 決賽 H.光輪2005  (閱讀 1496 次)

liouzhou_101

  • 初級會員
  • **
  • 文章數: 44
    • 檢視個人資料
NPSC 2005 高中組 決賽 H.光輪2005
« 於: 十一月 05, 2011, 11:22:10 pm »

題目簡述:
給出一個山形折線,兩人分別從左右山麓上山,最後同時到達最高的山峰,求出最少的轉彎次數。其中,在任意時刻兩人與水平面的距離保持相等。

題目分析:
乍看題目,感到毫無頭緒,很難抽象出模型,進而很難解決。
顯然,每個山峰(谷)的水準位置並無意義,可以略去。
而且這題的解法頗多,這裏僅介紹本人的一種解法:構造最短路模型。
儘量將原題中的一些狀態抽象成一些點,這些點之間可以互相到達,同時也有起點和目標點,於是就可以將原題轉為最短路模型,而狀態的表示則可以用DP來實現。
這裏,定義從左至右的山峰(穀)編號1至N,同時將左山麓抽象成山谷0,將右山麓抽象成山谷N+1。再定義每個山峰(穀)i左側的山坡為山坡i,這裏i=1,2,3,…,N+1。
設F(i,j)表示兩個人中有一個人在山峰(穀)i,而另一個人在山坡j的最少轉彎數。這便可得到F(i,j)的一些關係式。
將每個狀態(i,j)抽象成一個點,於是就可以構造出了最短路模型。
具體實現時非常複雜,要注意情況:
①   山峰(谷)i是山峰還是山谷
②   存在兩個或以上的山峰(穀)的高度相等,這個要特判。
具體細節可參考程式。

這題的做法應該不止此法,若有其他做法歡迎分享!

代碼: [選擇]
const
MaxN=210;

var
H : array[0..MaxN] of longint;
F : array[0..MaxN,0..MaxN] of longint;
qx,qy : array[1..100000] of longint;
top,n : longint;

procedure init;
var
i,flag : longint;
begin
H[0]:=0;
top:=0;
for i:=1 to n do begin
readln(flag,H[i]);
if H[top]<H[i] then top:=i;
end;
readln;
H[n+1]:=0;
end;

procedure work;                          //转最短路模型
var
i,j,head,tail,nowx,nowy,low,high,ans : longint;
procedure check(x,y:longint);
begin
if (x>=0) and (x<=n+1) and (y>=1) and (y<=n+1) then
if F[x,y]>F[nowx,nowy]+1 then begin
F[x,y]:=F[nowx,nowy]+1;
tail:=tail+1;
qx[tail]:=x;
qy[tail]:=y;
end;
end;
begin
for i:=0 to n+1 do
for j:=1 to n+1 do
F[i,j]:=1000000000;
F[0,n+1]:=0;
F[n+1,1]:=0;
head:=1;
tail:=2;
qx[1]:=0;
qy[1]:=n+1;
qx[2]:=n+1;
qy[2]:=1;
while head<=tail do begin
nowx:=qx[head];
nowy:=qy[head];
low:=nowy div 2*2;
high:=(nowy-1) div 2*2+1;
if nowx and 1=1 then begin   //山峰
if nowx-1>=0 then begin
if H[nowx-1]>=H[low] then
check(nowx-1,nowy);
if H[nowx-1]<=H[low] then
check(low,nowx);
if H[nowx-1]=H[low] then begin
if low<high then
check(nowx-1,nowy-1)
else
check(nowx-1,nowy+1);
check(low,nowx-1);
end;
end;
if nowx+1<=n+1 then begin
if H[nowx+1]>=H[low] then
check(nowx+1,nowy);
if H[nowx+1]<=H[low] then
check(low,nowx+1);
if H[nowx+1]=H[low] then begin
if low<high then
check(nowx+1,nowy-1)
else
check(nowx+1,nowy+1);
if nowx+2<=n+1 then
check(low,nowx+2);
end;
end;
end else begin               //山谷
if nowx-1>=0 then begin
if H[nowx-1]<=H[high] then
check(nowx-1,nowy);
if H[nowx-1]>=H[high] then
check(high,nowx);
if H[nowx-1]=H[high] then begin
if low<high then
check(nowx-1,nowy+1)
else
check(nowx-1,nowy-1);
check(high,nowx-1);
end;
end;
if nowx+1<=n+1 then begin
if H[nowx+1]<=H[high] then
check(nowx+1,nowy);
if H[nowx+1]>=H[high] then
check(high,nowx+1);
if H[nowx+1]=H[high] then begin
if low<high then
check(nowx+1,nowy+1)
else
check(nowx+1,nowy-1);
if nowx+2<=n+1 then
check(high,nowx+2);
end;
end;
end;
head:=head+1;
end;
if F[top,top]>F[top,top+1] then
ans:=F[top,top+1]
else
ans:=F[top,top];
if ans<1000000000 then
writeln(ans-1)
else
writeln('mission impossible');
end;

begin
while true do begin
readln(n);
if n=0 then break;
init;
work;
end;
end.
記錄

xavier13540

  • 新手
  • *
  • 文章數: 8
    • 檢視個人資料
Re: NPSC 2005 高中組 決賽 H.光輪2005
« 回覆 #1 於: 四月 04, 2018, 01:36:18 am »

構造一張圖 G = (V, E),其中
  • V 裡的任一元素代表兩人的所在位置,以無序對 (i, j) (若 hi = hj),或有序對 (i, j+1/2) (若 min{hj, hj+1} < hi < max{hj, hj+1}) 表示。
  • 設 u, v ∈ V。規定 uv ∈ E 若且唯若兩人可以在只上山或下山一次的情況下從 u 到達 v。
不難發現題目要問的就是從 (0, n+1) 到任意 (i, i) 的最短路徑長度減 1,可用一次 BFS 解決。因為 |V| = O(n2),且每個頂點的度數 (degree) 都不超過 4,可知整體的時間複雜度是 O(n2)。
值得一提的是,一定存在一條從 (0, n+1) 到某個 (i, i) 的路徑。我們把 G 裡的頂點分成下面這幾種,並討論它們的度數。
  • (0, 0), (0, n+1), (n+1, n+1) 的度數都是 1。
  • 若 i ≠ 0, n+1 且 hi = 0,則 (0, i) 和 (i, n+1) 的度數都是 2。
  • 若 i ≠ 0, n+1,則 (i, i) 的度數是 3。
  • 若 i ≠ j 且 hi = hj,則 (i, j) 的度數是 4 (若 i, j 同為山頂或山谷) 或 0 (若 i, j 一者是山頂另一者是山谷)。
  • 設 v := (i, j+1/2) 為一合法頂點,則 v 的度數是 2。
令 H 為 G 中包含頂點 (0, n+1) 的連通部分 (connected component)。因為 H 的頂點度數和為偶數,可知 H 必定包含某個 (i, i),亦即存在從 (0, n+1) 到某個 (i, i) 的路徑。

以下是我的 C++ code:
代碼: [選擇]
#include<cassert>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

#define N 210
typedef pair<int, int> pii;
int n, h[2*N];
vector<int> g[4*N*N];
bool vis[4*N*N];
int state(int i, int j){
    if(i > j){
        swap(i, j);
    }
    return i*(2*n+3)+j;
}
int move(int i, int j, int di, int dj){
    int c = (i&2)-1;
    if(j&1){
        if(c*h[i+2*di] < c*h[j+dj]){
            return state(i+di, j+dj);
        }else if(c*h[i+2*di] == c*h[j+dj]){
            return state(i+2*di, j+dj);
        }else{
            return state(i+2*di, j);
        }
    }else{
        if(c*h[i+2*di] < c*h[j+2*dj]){
            return state(i+di, j+2*dj);
        }else if(c*h[i+2*di] == c*h[j+2*dj]){
            return state(i+2*di, j+2*dj);
        }else{
            return state(i+2*di, j+dj);
        }
    }
}
bool meet(int v){
    return v/(2*n+3) == v%(2*n+3);
}

int main(){
    while(scanf("%d", &n), n){
        h[0] = h[2*n+2] = 0;
        for(int i=1; i<=n; i++){
            scanf("%*d%d", h+2*i);
        }
        scanf("%*d");
        for(int i=0; i<(2*n+3)*(2*n+3); i++){
            g[i].clear();
        }
        g[state(0, 0)].push_back(move(0, 0, 1, 1));
        g[state(0, 2*n+2)].push_back(move(0, 2*n+2, 1, -1));
        g[state(2*n+2, 2*n+2)].push_back(move(2*n+2, 2*n+2, -1, -1));
        for(int j=4; j<=2*n-2; j+=4) if(h[j] == 0){
            g[state(0, j)].push_back(move(0, j, 1, -1));
            g[state(0, j)].push_back(move(0, j, 1, 1));
            g[state(j, 2*n+2)].push_back(move(j, 2*n+2, -1, -1));
            g[state(j, 2*n+2)].push_back(move(j, 2*n+2, 1, -1));
        }
        for(int i=2, c=1; i<=2*n; i+=2, c*=(-1)){
            for(int j=i; j<=2*n; j+=4) if(h[i] == h[j]){
                g[state(i, j)].push_back(move(i, j, -1, -1));
                g[state(i, j)].push_back(move(i, j, -1, 1));
                g[state(i, j)].push_back(move(i, j, 1, -1));
                g[state(i, j)].push_back(move(i, j, 1, 1));
            }
            for(int j=1; j<=2*n-1; j+=4) if(h[j-1]<h[i] && h[i]<h[j+1]){
                g[state(i, j)].push_back(move(i, j, -1, -c));
                g[state(i, j)].push_back(move(i, j, 1, -c));
            }
            for(int j=3; j<=2*n+1; j+=4) if(h[j-1]>h[i] && h[i]>h[j+1]){
                g[state(i, j)].push_back(move(i, j, -1, c));
                g[state(i, j)].push_back(move(i, j, 1, c));
            }
        }
        bool sol = false;
        memset(vis, false, sizeof(vis));
        queue<pii> bfs;
        bfs.push(make_pair(0, state(0, 2*n+2)));
        vis[state(0, 2*n+2)] = true;
        while(!bfs.empty()){
            pii p = bfs.front(); bfs.pop();
            int d=p.first, v=p.second;
            if(meet(v)){
                printf("%d\n", d-1);
                sol=true; break;
            }
            for(int i=0; i<(int)g[v].size(); i++) if(!vis[g[v][i]]){
                bfs.push(make_pair(d+1, g[v][i]));
                vis[g[v][i]] = true;
            }
        }
        assert(sol);
    }
    return 0;
}

« 上次編輯: 四月 07, 2018, 01:25:18 am 由 xavier13540 »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 H.光輪2005