Posted on 2012-02-25 08:50
C小加 閱讀(555)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
解題報(bào)告
DP。
１、每一行最多只可以走一次捷徑，每一列也是最多只可以走一次捷徑
２、每次走過捷徑后的橫坐標(biāo)和縱坐標(biāo)都要大于之前的坐標(biāo)
只要求出從起點(diǎn)到終點(diǎn)所經(jīng)過的最多的捷徑，就能得到最少的路程。每一步的最優(yōu)解用之前走過的路徑所求，滿足無后效性，每一個(gè)子狀態(tài)都可以求出最優(yōu)解，滿足最優(yōu)子結(jié)構(gòu)，可以用dp解決。
f[i]=max(f[j]+1,f[i]);
當(dāng)j點(diǎn)坐標(biāo)小于點(diǎn)，i點(diǎn)為捷徑時(shí)，走到i點(diǎn)坐標(biāo)時(shí)經(jīng)過的最多捷徑數(shù)=max(走到j點(diǎn)的最多捷徑數(shù)+1，走到i點(diǎn)時(shí)的最多捷徑數(shù))
最后找出最大的f(i)就是能經(jīng)過最多的捷徑
注意坐標(biāo)的輸入沒有順序性，要進(jìn)行排列。
#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);
//如果橫坐標(biāo)相等，按照縱坐標(biāo)從小到大排序，否則按照橫坐標(biāo)從小到大排序
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]);
}
}
}
//求用到最多捷徑的點(diǎn)
int ma=*max_element(f,f+k);
cout<<(
int)((m+n-2*ma)*100+ma*100*sqrt(2.0)+0.5)<<endl;
}
return 0;
}