已知藏宝图上标有若干个排成一条直线的魔法石矿，每个矿里有一定数量的魔法石，如表所示：
藏宝图上还给出挖完每个矿之后可以挖哪些矿。挖矿规则为可以从任何一个矿开始，到任何一个矿结束。同时挖完这个矿后，只能选择一个后续的矿继续挖，并且只能向右挖，不能回头向左挖。请问如何能挖出最多的矿石。
输入 第一行为一个整数n，表示有n（n<=1000）个矿。第二行为n个整数，表示这n个矿里面的魔法石数。随后n行表示每个矿挖完后还能再挖哪些矿。 输出 最多挖出的魔法石数 输入示例 3 1 1 1 1 2 3 2 3 3 输出示例 3#include <iostream> #include <cstdio> #define MAXN = 100 + 10 using namespace std; long long a[10010],dp[10010],book[1010][1010],flag[10010]; int main() { //freopen(".in","r",stdin); //freopen(".out","w",stdout); int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { char c; int x; cin>>x; if(i!=x) book[i][x]=1; while(1) { c=getchar(); if(c==' ') { cin>>x; if(i!=x) book[i][x]=1; } if(c=='\n') break; } } for(int i=1;i<=n;i++) dp[i]=a[i]; /*for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout<<book[i][j]<<" "; cout<<endl; }*/ for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(book[i][j]==1) dp[j]=max(dp[j],dp[i]+a[j]); sort(dp,dp+n+1); cout<<dp[n]; //system("pause"); } /* if(book[i][j]==1) { dp[i]=max(); } 1 2 3 1 2 5 */ View Code
转载于:https://www.cnblogs.com/jason2003/p/6616496.html
相关资源：【防检测 防封高科技】流量矿石多开 再也不用虚拟机