Posted on 2012-02-25 08:50
C小加 閱讀(550)
評論(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;
}