Posted on 2012-02-25 08:50
C小加 阅读(544)
评论(1) 编辑 收藏 引用 所属分类:
解题报告
DP。
１、每一行最多只可以走一次捷径，每一列也是最多只可以走一次捷径
２、每次走过捷径后的横坐标和纵坐标都要大于之前的坐标
只要求出从起点到终点所经过的最多的捷径，就能得到最少的路程。每一步的最优解用之前走过的路径所求，满足无后效性，每一个子状态都可以求出最优解，满足最优子结构，可以用dp解决。
f[i]=max(f[j]+1,f[i]);
当j点坐标小于点，i点为捷径时，走到i点坐标时经过的最多捷径数=max(走到j点的最多捷径数+1，走到i点时的最多捷径数)
最后找出最大的f(i)就是能经过最多的捷径
注意坐标的输入没有顺序性，要进行排列。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int MAXN=1003;
typedef
struct{
int a,b;
}point;
point p[MAXN];
int f[1003];
bool cmp(point p1,point p2)
{
if(p1.a==p2.a)
return p1.b<p2.b;
return p1.a<p2.a;
}
int main()
{
//freopen("1.in","r",stdin);
int m,n;
while(cin>>n>>m)
{
int k;
cin>>k;
for(
int i=0;i<k;i++)
{
cin>>p[i].a>>p[i].b;
f[i]=1;
}
sort(p,p+k,cmp);
//如果横坐标相等，按照纵坐标从小到大排序，否则按照横坐标从小到大排序
int v=0,flag=0;
//dp
for(
int i=0;i<k;i++)
{
for(
int j=0;j<=i;j++)
{
if(p[i].a>p[j].a)
{
if(p[i].b>p[j].b) f[i]=max(f[j]+1,f[i]);
}
}
}
//求用到最多捷径的点
int ma=*max_element(f,f+k);
cout<<(
int)((m+n-2*ma)*100+ma*100*sqrt(2.0)+0.5)<<endl;
}
return 0;
}