NYOJ-195飛翔

4039 ワード

フライング
時間制限:3000 ms|メモリ制限:65535 KB
難易度:4

説明
鷹が一番誇りに思っているのは飛ぶことですが、鷹たちはお互いに他の鷹が自分より速く飛ぶことに嫉妬し、他の鷹が自分より飛ぶ技術に嫉妬しています.そこで、彼らは試合を開催することにしました.試合の場所は迷宮の中にあります.
これらのイーグルの開始点は、N*M行列の左下角map[1,1]の左下角に設けられる.終点は行列の右上隅map[N,M]の右上隅に設定され,一部のmap[i,j]は中間から通り抜けることができる.各四角形の辺の長さは100メートルです.図に示すように、

障害もなく、死の道もない.このような設計は主に高速飛行の鷹たちが死路が調整に間に合わないことを発見しないために意外になった.パンパス雄鷹はRPを減らす危険を冒して試合主催者の警備が厳しい基地から工事の地図を盗んだ.しかし問題も伴い、試合が始まる前に地図のすべての道を明らかにし、ゴールに一番近い道を見つけなければならない.(ははは、愚かな鳥は先に飛ばさなくてもチャンピオンになる)しかし、この鷹は前には古鷹がなく、後には鷹の料理を食べて育った鷹--菜鳥である.彼は自分で最も短い道を得ることができなくて、そこで緊急の下でOIを学ぶあなたを見つけて、あなたの助けを見つけたいです.

入力
この問題には複数のデータがあります.EOFを入力終了のフラグとします.各試験データのセットの最初の挙動n,m(0しゅつりょく
1行、1-->n、mの最短経路の長さだけを整数に四捨五入して保持すればよい
サンプル入力

サンプル出力

/*
   ：
           ，             ，         ，   
        。。。。。。
#include <cstdio>
#include <cmath>
#include <iostream>

using namespace std;

const int N = 1001;
bool map[N][N];

double min1(double x, double y, double z)
{
    if(x - y > 1e-6)
    {
        if(x - z > 1e-6)
            return x;
        return z;
    }
    else if(y - z > 1e-6)
        return y;
    return z;
}

double min2(double x, double y)
{
    if(x - y > 1e-6)
        return x;
    return y;
}
double dis(int n, int m)
{
    if(n == 1 && m ==1)
        return 0;
    if(n == 1)
        return 1 + dis(1, m - 1);
    if(m == 1)
        return 1 + dis(n - 1, 1);
    if(map[n - 1][m - 1])
        return min1(dis(n-1, m) + 1, dis(n, m-1) + 1, sqrt(2.0) + dis(n-1, m-1));
    else
        return min2(1 + dis(n-1, m), 1 + dis(n, m-1));
}

int main()
{
    int n, m, k, i, j;
    while(~scanf("%d%d", &n, &m))
    {
        memset(map, false, sizeof(map));
        scanf("%d", &k);
        while(k--)
        {
            scanf("%d%d", &i, &j);
            map[i][j] = true;
        }
        printf("%d
", dis(n, m));
    }
    return 0;
}

   ：-------AC
               ，             */
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

struct node
{
    int x;
    int y;
}a[1001];

bool cmp(node p1, node p2)
{
    if(p1.x == p2.x)
        return p1.y < p2.y;
    return p1.x < p2.x;
}

int solve(int n)
{
    int cnt[1001];
    int max = 0;
    for(int i = 0; i < n; ++i)
    {
        cnt[i] = 1;
        for(int j = 0; j < i; ++j)
        {
            if(a[i].y > a[j].y && a[i].x > a[j].x && cnt[i] < cnt[j] + 1)
                cnt[i] = cnt[j] + 1;
        }
        if(max < cnt[i])
            max = cnt[i];
    }
    return max;
}

int main()
{
    int m, n, k, p;
    while(~scanf("%d%d", &n, &m))
    {
        scanf("%d", &k);
        for(int i = 0; i < k; ++i)
        {
            scanf("%d%d", &a[i].x, &a[i].y);
        }
        sort(a, a + k, cmp);
        //                ，             0   
        printf("%.0lf
", (n + m - ((2 - sqrt(2)) * solve(k)))* 100);
    }
    return 0;
}

vimテクニックコレクション