Problem F. Jhadgre的伤心地

题目描述 

Jhadgre为了他的女神,准备了一场盛大的告白,可惜却被女神毫不留情的拒绝。于是Jhadgre决定离开这个伤心之地。但是钱都被Jhadgre拿去准备告白了,剩下的钱并不够他买车票,只够他坐公交车。

Jhadgre所在城市的所有公交车站总体来说都在一条直线上,在这里有两种公交车,一种是全城公交,这种公交车在城市的任何一站都可以上下车,付了车费后,从当前站开始,最多可以向后坐5站(即从第i站上车,可以选择在第i+1,i+2,i+3,i+4,i+5站下车)。还有一种是区间公交,也就是可以在第X站上车,直到第Y站(X<Y),中途每一站都可以下车但不可以上车。所有公交车的上车费都是2元。

现在Jhadgre为了最快的逃离这个伤心地,他决定不管上哪种公交车,只要上去了,就一定坐到底再下车,中途不会下车,并且他现在所在的地点为第1站,他认为要到第N站以后的站,他才算彻底逃离这个伤心地。

现在Jhadgre想知道他手里的钱够不够逃离这个伤心地,你可以帮他计算一下他最少需要花多少钱才能离开这个伤心地吗?

输入描述:

只包含一组数据。
第一行一个整数N,意义如题(10<=N<=100)
接下去一行中共N个整数a1,a2,a3...aN,由空格隔开,ai表示第i站的区间公交能到达第ai站,保证(i<ai)

输出描述:

Jhadgre最少需要花的钱

示例1

输入

10
7 11 4 5 6 7 8 9 10 11

输出

4

说明

以下给出两种乘车方案:

(1) Jhadgre在第1站选择上全城公交,到达第6站,付2元钱,接着在第6站选择上全城公交,到达第11站,共付4元钱。

(2) Jhadgre在第1站选择上区间公交,到达第7站,付2元钱,接着在第7站选择上全城公交,到达第12站,共付4元钱。

题解:简单的区间DP,题目可以转换为最少做几次公交车,D[i][j]的含义为从i到j点最少需要多少钱。

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define EPS 1e-8
#define maxn 110
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
using namespace std;
int n,mx,ans;
int A[maxn],D[maxn][maxn];
int main()
{
    scanf("%d",&n);
    mx=0;
    ans=INF;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&A[i]);
        D[i][i+5]=2;
        D[i][A[i]]=2;
        mx=max(mx,A[i]);
    }
    mx=max(mx,n+5);
    for (int i=1;i<=mx;i++)
    {
        for (int j=1;j<=mx;j++)
        {
            D[i][j]=INF;
        }
        D[i][i]=0;
        D[i][i+5]=2;
        D[i][A[i]]=2;
    }
    for (int i=1;i<=mx;i++)
    {
        for (int j=1;j<=n;j++)
        {
            D[1][i]=min(D[1][i],D[1][j]+D[j][i]);
        }
    }
    for (int i=n+1;i<=mx;i++)
    {
        if (D[1][i]!=INF)
        {
            ans=min(ans,D[1][i]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

 

官方的题解就很简洁了,直接递归调用,fun()函数的含义就是从x点出发到达终点最少的乘车次数

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000];
int fun(int x){
if (x > n) return 0;
return min(fun(a[x]),fun(x + 5)) + 1;
}
int main()
{
scanf("%d",&n);
for (int i = 1 ; i <= n ; ++i)
scanf("%d",&a[i]);
cout<< fun(1) * 2<<endl; 
return 0;
}

 

发表评论,支持MarkDown语法