SSL 1748_飞翔_dp+离散

发布于 2019-04-30  7 次阅读


题目描述

 这些鹰的起始点被设在一个N*M矩阵的左下角map[1,1]的左下角。终点被设定在矩阵的右上角map[N,M]的右上角,有些map[i,j]是可以从中间穿越的。每一个方格的边长都是100米。如图所示:
这里写图片描述


思路

离散了以后用最长不下降子序列求解
就是排序一下找到一个有最多特殊路径的上升的路就可以了


#include 
#include 
#include 
using namespace std;
struct arr
{
    int x,y;
}a[10000];
int f[10000];
int camp(arr a,arr b)
{
    if (a.x==b.x)  
        return a.yt)
                t=f[j]+1;
        }
        f[i]=t;
    }
    int t=0;
    for (int i=1;i<=l;i++)
        if (f[i]>t) t=f[i];
    printf("%.0lf\n",(n+m-2*t+sqrt(2)*t)*100);
}
]]>