【動態規劃】魔法石礦
時間限制: 1 Sec 內存限制: 64 MB
提交: 116 解決: 27
[提交] [狀態] [命題人:admin]
題目描述
為了找到回家的路，張琪曼施展魔法，從高維空間召喚出了一種叫作“讀者”的生物，據說“讀者”這種生物無所不能，他們可以穿越時空的限制，聆聽到歷史的聲音、巨人的吶喊。但這次“讀者”卻很嚴肅地警告她們，從遠古起就陰魂不散的天頂星人已沖破封印再次降臨到了這個空間，她們若不早做準備，不僅她們所在的這個世界將變成修羅場，連“讀者”所在的時空也會受到牽連。最后“讀者”交給她們一張藏寶圖希望她們能收集足夠多的魔法石能量以對抗天頂星人的進攻。已知藏寶圖上標有若干個排成一條直線的魔法石礦，每個礦里有一定數量的魔法石，如表所示。

同時每個礦中都有一張說明書，說明在挖完此礦的魔法石后還可繼續挖哪些礦，如圖所示。

挖礦規則為可以從任何一個礦開始，到任何一個礦結束，同時挖完這個礦中的魔法石之后，可以選擇它可繼續挖的礦之一繼續挖，但只能選擇一條。如挖完1礦后，可挖2礦，再挖5礦，6礦，……但只可以向右挖，不能回頭向左挖。請問如何挖才能挖出最多的魔法石？

輸入
第一行為一個整數n，表示有n（n≤1000）個礦。第二行為n個整數，表示這n個礦的魔法石數。隨后n行表示每個礦挖完后還能再挖哪些礦。

輸出
最多挖出的魔法石數。

樣例輸入
復制樣例數據
3
1 1 1
1 2 3
2 3
3
樣例輸出
3

解題思路：
我們可以用$dp[i]$來表示到達$i$號礦坑所能獲得的最大礦石數，則：
$dp[i]=max(dp[i],dp[j]+num[i])$ $j$代表$j$號礦坑能從$i$號礦坑的左部到達$i$號礦坑

代碼：

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
ll dp[1200];
vector<int> a[1200];
ll num[1200];
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);int n;scanf("%d",&n);rep(i,1,n) {scanf("%lld",&num[i]);dp[i]=num[i];}char c;int nape=0;int x;for(int i=1;i<=n;i++) {scanf("%d",&x);do{nape=0;while(1) {c=getchar();if(c>='0'&&c<='9') {nape=nape*10+(c-'0');}elsebreak;}if(nape>0&&nape!=i) {a[nape].push_back(i);}}while(c!='\n');}rep(i,1,n) {for(int j=0;j<a[i].size();j++) {dp[i]=max(dp[i],dp[a[i][j]]+num[i]);}}ll ans=0;rep(i,1,n) {ans=max(ans,dp[i]);}printf("%lld\n",ans);return 0;
}