Nyoj 195

1792 단어 dp
오랫동안 보았지만 제목이 무슨 뜻인지 멍하니 이해하지 못했다.한바탕 미치광이!
제목은 (0, 0) 점에서 (n, m) 점으로 날아가는 데 가장 짧은 거리가 얼마라는 뜻이다.그 중 어떤 것은 네모난 대각선(즉 지름길)을 걸을 수 있고, 만약 네모난 칸이 대각선을 걸을 수 없다면 네모난 칸의 두 변만 걸을 수 있다.
만약에 지름길을 갈 수 있다면 한 점(x1, y1)에서 다른 점(x2, y2)으로 갈 수 있기 때문에 x2>x1 & & y2>y1, 즉 한 줄에 여러 줄로 지름길만 갈 수 있기 때문에 먼저 지름길로 갈 수 있는 점을 정렬할 수 있다. dp[i]에는 i점으로 갈 수 있는 최대 지름길이 저장되어 있는데 dp[i]=MAX(dp[i], dp[j]+1)가 있고 그 중에서 i>j&Pointi]가 있다.x > Point[i].x && Point[i].y > Point[j].y; 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN = 1010;

int dp[MAXN];

struct Node
{
    int x;
    int y;
};

Node Point[MAXN];

int Cmp(const void* a, const void* b)
{
    Node* aa = (Node *)a;
    Node* bb = (Node *)b;
    if(aa->x == bb->x)
        return aa->y - bb->y;
    return aa->x - bb->x;
}

int Find_Road( int n)
{
    int dp[MAXN];
    memset(dp, 0, sizeof(dp));
    int num = 0;
    for(int i = 0; i < n; ++i)
    {
        dp[i] = 1;
        for(int j = 0; j < i; ++j)
        {
            if(Point[i].x > Point[j].x && Point[i].y > Point[j].y && dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        }
        if(dp[i] > num)
            num = dp[i];
    }
    return num;
}

int main()
{
    int n, m;
    int k;
    while(~scanf("%d %d", &n, &m))
    {
        cin>>k;
        for(int i = 0; i < k; ++i)
        {
            cin>>Point[i].x>>Point[i].y;
        }
        qsort(Point, k, sizeof(Point[0]), Cmp);
        int s = Find_Road(k);
        cout<<(int)( (m+n - s*(2 - sqrt(2)))*100 + 0.5 )<<endl;
    }
    return 0;
}
코드 초보자 CSS 아트pt.셋
28일째 포트폴리오 제작

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage