Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

PKU 1008 滑雪

Posted on 2007-05-19 22:19 ZelluX 阅读(276) 评论(0)  编辑  收藏 所属分类: Algorithm

5.19
第一反应觉得是个简单的BFS,从最高点开始向四周扩展,最后找到最长的路径即可。
结果Wrong Answer,仔细一想,才意识到并不一定是从最高点开始的。考虑得太不周到了。。

5.31
原来的程序找不到了。。。重新写了一遍,居然写好提交就AC了,恩。这几天进步挺大哈

#include <iostream>
#include 
<fstream>
#include 
<algorithm>
#include 
<vector>

using namespace std;

const int MAX_HEIGHT = 10000;
const int MAX_ROWS = 100;
const int dx[] = {00-11};
const int dy[] = {1-100};

struct Point {
    
int x;
    
int y;
    
int height;
}
;

bool comparePoints(const Point& p1, const Point& p2);
int main() {
    
//ifstream fin("pku1088.in");
    int c, r;
    
int i, j;
    cin 
>> r >> c;
    
int h[MAX_ROWS + 2][MAX_ROWS + 2];
    
int count = 0;
    vector
<Point> points;
    
for (i = 1; i <= r; i++{
        
for (j = 1; j <= c; j++{
            cin 
>> h[i][j];
            Point temp;
            temp.x 
= i;
            temp.y 
= j;
            temp.height 
= h[i][j];
            points.push_back(temp);
        }

    }


    sort(points.begin(), points.end(), comparePoints);
    
    
for (i = 0; i <= c; i++{
        h[
0][i] = MAX_HEIGHT + 1;
        h[r 
+ 1][i] = MAX_HEIGHT + 1;
    }

    
for (i = 0; i <= r; i++{
        h[i][
0= MAX_HEIGHT + 1;
        h[i][c 
+ 1= MAX_HEIGHT + 1;
    }


    
int f[MAX_ROWS + 1][MAX_ROWS + 1];
    
for (i = 1; i <= r; i++{
        
for (int j = 1; j <= c; j++{
            f[i][j] 
= 1;
        }

    }

    
    vector
<Point>::iterator iter;
    
for (iter = points.begin(); iter != points.end(); iter++{
        
for (i = 0; i < 4; i++{
            
int nx = iter->+ dx[i];
            
int ny = iter->+ dy[i];
            
if (iter->height > h[nx][ny]) {
                
if (f[iter->x][iter->y] + 1 > f[nx][ny]) {
                    f[nx][ny] 
= f[iter->x][iter->y] + 1;
                }

            }

        }

    }


    
int best = 0;
    
for (i = 1; i <= r; i++{
        
for (j = 1; j <= c; j++{
            
if (f[i][j] > best) {
                best 
= f[i][j];
            }

        }

    }

    cout 
<< best << endl;
    
return 0;
}


bool comparePoints(const Point& p1, const Point& p2) {
    
return (p1.height > p2.height);
}

只有注册用户登录后才能发表评论。


网站导航: