魔法石矿

http://www.razxhoi.com/mod/programming/view.php?id=5386
【题目描述】魔法石矿(Mine.cpp/c/pas)

为了找到回家的路,张琪曼施展魔法,从高维空间召唤出了一种叫作“读者”的生物,据说“读者”这种生物无所不能,他们可以穿越时空的限制,聆听到历史的声音、巨人的呐喊。但这次“读者”却很严肃地警告她们,从远古起就阴魂不散的天顶星人已冲破封印再次降临到了这个空间,她们若不早做准备,不仅她们所在的这个世界将变成修罗场,连“读者”所在的时空也会受到牵连。最后“读者”交给她们一张藏宝图希望她们能收集足够多的魔法石能量以对抗天顶星人的进攻。已知藏宝图上标有若干个排成一条直线的魔法石矿,每个矿里有一定数量的魔法石,如表所示。
同时每个矿中都有一张说明书,说明在挖完此矿的魔法石后还可继续挖哪些矿,如图所示。
挖矿规则为可以从任何一个矿开始,到任何一个矿结束,同时挖完这个矿中的魔法石之后,可以选择它可继续挖的矿之一继续挖,但只能选择一条。如挖完1矿后,可挖2矿,再挖5矿,6矿,……但只可以向右挖,不能回头向左挖。请问如何挖才能挖出最多的魔法石?

【输入格式】

第一行为一个整数n,表示有n(n≤1000)个矿。第二行为n个整数,表示这n个矿的魔法石数。随后n行表示每个矿挖完后还能再挖哪些矿。

【输出格式】

最多挖出的魔法石数。

【输入样例】
3
1 1 1
1 2 3
2 3
3

【输出样例】

3
题解:这是一道典型的最大上升子序列,但是数据中没有说明每行个数有多少个,所以要用字符串流来处理。
注意:数据中间可能有换行,所以在读字符串流前要读走一个换行。
代码时间复杂度O(n2)

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[1005],f[1005][1005],b[1005],n;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    freopen("Mine.in","r",stdin);
    freopen("Mine.out","w",stdout);
    int i,j,x;
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    string s;
    getline(cin,s);
    for(i=1; i<=n; i++)
    {
        getline(cin,s);
        stringstream ss(s);
        string s1;
        while(ss>>x)
        {
            f[i][x]=1;
        }
    }
    int maxn=0;
    b[1]=a[1];
    for(i=2; i<=n; i++)
    {
        b[i]=max(b[i],a[i]);
        for(j=1; j<i; j++)
        {
            if(f[j][i]==1)
            {
                b[i]=max(b[i],b[j]+a[i]);
            }
        }
    }
    for(i=1; i<=n; i++)
        maxn=max(maxn,b[i]);
    cout<<maxn<<endl;
    return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
大方的大熊猫准备进厂:1.教育背景:你希望从事什么专业的工作你的主修课就是什么;成绩优秀是你应该做的,没什么可描述的,成绩不优秀也许人家在大学忙着创业呢?(成绩优秀不一定是好事,只能说明多元化的大学你上成了高中,没有真正上明白大学,反而体现了你死板,不爱社交,没有别的突出能力) 2.实践经历:你想表达的意思没有说清楚。你是说你会个性化服务,还是你有实习经历。如果没有带来,经济收益,表彰,更好的发展前景,那你还不如说说提升了自己哪些技能。你说有人给你送锦旗我都能明白你优秀,但是你说你会xxxx,你说这话谁信,证据呢。 3.入伍经历:你描述的就是你的工作职责或者你应该做的,并没有体现出来你把这个事情做好了,而且入伍经历并不能证明你能干好你要应聘的工作,不如只写经历其余所有内容都不写。 4.荣誉技能:重点突出一下,但不要过多描述,这些荣誉的含金量懂得都懂。 重点:你要应聘什么工作(具体岗位,实习生不具体),你的期望薪资
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务