NYOJ 10 skiing (深搜和動歸)
來源：程序員人生 發布時間：2014-11-11 08:32:00 閱讀次數：2716次
skiing
時間限制：3000 ms | 內存限制：65535 KB
難度：5
-
描寫
- Michael喜歡滑雪百這其實不奇怪， 由于滑雪的確很刺激。可是為了取得速度，滑的區域必須向下傾斜，而且當你滑到坡底，你不能不再次走上坡或等待升降機來載你。Michael想知道載1個區域中最長底滑坡。區域由1個2維數組給出。數組的每一個數字代表點的高度。下面是1個例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
1個人可以從某個點滑向上下左右相鄰4個點之1，當且僅當高度減小。在上面的例子中，1條可滑行的滑坡為24⑴7⑴6⑴。固然25⑵4⑵3-...⑶⑵⑴更長。事實上，這是最長的1條。
-
輸入
- 第1行表示有幾組測試數據，輸入的第2行表示區域的行數R和列數C(1 <= R,C <= 100)。下面是R行，每行有C個整數，代表高度h，0<=h<=10000。
后面是下1組數據；
-
輸出
- 輸出最長區域的長度。
算法分析：
1看本題就感覺這不是才看過的單調遞減子序列問題么，但這個難點在于數據其實不是線性的，每步都有4個方向可走，因而乎，，深搜解此題必須是易如反掌啊。。注意中間的剪枝問題，利用記憶話數組去除重復的計算類似于遞歸型DP，下面看1個來自網上的深搜代碼：
#include<stdio.h>
#include<string.h>
int a[101][101],visit[101][101];
int dx[4]={0,0,1,⑴};
int dy[4]={1,⑴,0,0};
int s,t,max,r,c;
int bfs(int x,int y)
{
if(visit[x][y]>1)//**剪枝，不剪枝應當是TLE的，測試數據有點弱，不過就算沒TLE，加了剪枝的時間優化了很多*//
{
return visit[x][y];//**如果之前搜索過這點，就直接返回搜索的這點，不用再進行搜索**//
}
for(int k=0;k<4;k++)
{
s=x+dx[k];
t=y+dy[k];
if(s>=0 && s<r && t>=0 && t<c && a[x][y]<a[s][t])//**搜索的范圍。DP看做單調遞增數列**//
{
max=bfs(s,t);//**動態計劃**//
if(visit[x][y]<max+1)
{
visit[x][y]=max+1;
}
}
}
return visit[x][y];//**返回這點能獲得的最大值**//
}
int main()
{
int ncases,i,j,ans;
scanf("%d",&ncases);
while(ncases--)
{
ans=⑴;
scanf("%d %d",&r,&c);
for(i=0;i<=r⑴;i++)
{
for(j=0;j<=c⑴;j++)
{
scanf("%d",&a[i][j]);
visit[i][j]=1;
}
}
for(i=0;i<=r⑴;i++)
{
for(j=0;j<=c⑴;j++)
{
bfs(i,j);
if(visit[i][j]>ans)
{
ans=visit[i][j];
}
}
}
printf("%d
",ans);
}
return 0;
}
注意，這里為了保證以任意出發點開始搜索，必須要以m*n個出發點進行向下深搜，這也自然使得時間復雜度提升了，因而乎我選擇的是人人為我型動歸，以其他4個方向的值來不斷更新當前點的值，然后不斷進行遞推，但問題來了，為了使得每次遞歸都以當前最低位置開始，那末每次遞推的出發點怎樣肯定呢？？？這里我的確被坑了1下，想了各種不同的方案，比如，增設1維數組來保存map,j進行排序，但怎樣返回坐標呢，以后我有通過雙循環不斷產生去除上1個最低位置后的最低位置，但這不是比深搜還有麻煩，最后無奈之下，結構體走起。。。問題就直接解決了
#include<iostream>
#include<algorithm>
using namespace std;
int map[101][101];
int d[101][101];
struct node{
int x,y;
int value;
}tmap[10001];
int K;
int dir[2][4]={{1,0,⑴,0},{0,1,0,⑴}};
int max(int a,int b)
{return a>b?a:b;}
int comp(node a,node b)
{
return a.value<b.value;
}
int dp(int m,int n)
{
int i,j,k,x,y,ans=0,p;
for(p=0;p<K;p++)
{
i=tmap[p].x;
j=tmap[p].y;
for(k=0;k<4;k++)
{
x=i+dir[0][k];
y=j+dir[1][k];
if(x>=1&&x<=m&&y>=1&&y<=n&&map[x][y]<map[i][j])
d[i][j]=max(d[i][j],d[x][y]+1);
ans=ans>d[i][j]?ans:d[i][j];
}
}
return ans;
}
int main()
{
int N,m,n,i,j;
cin>>N;
while(N--)
{
K=0;
cin>>m>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
cin>>map[i][j];
d[i][j]=1;
tmap[K].x=i;
tmap[K].y=j;
tmap[K++].value=map[i][j];
}
sort(tmap,tmap+K,comp);
cout<<dp(m,n)<<endl;
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
