PID30 / [stupid]愚蠢的矿工☆
背景
Stupid 家族得知在HYC家的后花园里的中央花坛处,向北走3步,向西走3步,再向北走3步,向东走3步,再向北走6步,向东走3步,向南走12步,再向西走2步( - -||)就能找到宝藏的入口,而且宝藏都是藏在山里的,必须挖出来,于是Stupid家族派狗狗带领矿工队去挖宝藏.(HYC家的宝藏被狗狗挖走后有什么感想?)
描述
这个宝藏的制造者为了掩盖世人耳目,他做的宝藏是没有出口,只有入口,不少建造宝藏的人都死在里面.现在知道宝藏总共有N个分岔口,在分岔口处是有财宝的,每个宝藏点都有一个财富值.狗狗只带了M个人来,而且为了安全起见,在每个分岔口,必须至少留一个人下来,这个留下来的人可以挖宝藏(每个人只能挖一个地方的宝藏),这样才能保证不会迷路,而且这个迷宫有个特点,任意两点间有且只有一条路可通.狗狗为了让他的00开心,决定要尽可能地多挖些宝藏回去.现在狗狗的圈叉电脑不在身旁,只能求救于你了,你要知道,狗狗的终身幸福就在你手上了..(狗狗ps:00,你不能就这样抛弃偶……)
输入格式
第1行:两个正整数N,M .N表示宝藏点的个数,M表示狗狗带去的人数(那是一条懒狗,他自己可不做事)。(n<=1000,m<=100)
第2行:N个整数,第i个整数表示第i个宝藏的财富值.(保证|wi|<maxint)
第N+2行:两个非负整数A和B,表示A通向B,当A=0,表示A是入口.(保证A,B<=n)
输出格式
输出狗狗能带回去的宝藏的价值。
样例输入
4 3
5 6 2 4
1 2
0 1
2 3
3 4
样例输出
13
code
1 #include<cstdio> 2 #include<algorithm> 3 4 using namespace std; 5 const int MAXN = 1010; 6 struct Edge{ 7 int to,nxt; 8 }e[10010]; 9 int c[MAXN],f[MAXN][110],head[MAXN]; 10 int n,m,tot; 11 12 void add_edge(int u,int v) 13 { 14 e[++tot].to = v;e[tot].nxt = head[u]; 15 head[u] = tot; 16 } 17 void dp(int u,int t) 18 { 19 if (t<=0) return ; 20 for (int i=head[u]; i; i=e[i].nxt) 21 { 22 int v = e[i].to; 23 for (int k=0; k<t; ++k) 24 f[v][k] = f[u][k]+c[v]; 25 dp(v,t-1); 26 for (int k=1; k<=t; ++k) 27 f[u][k] = max(f[u][k],f[v][k-1]); 28 } 29 } 30 int main() 31 { 32 scanf("%d%d",&n,&m); 33 for (int i=1; i<=n; ++i) 34 scanf("%d",&c[i]); 35 for (int x,y,i=1; i<=n; ++i) 36 { 37 scanf("%d%d",&x,&y); 38 add_edge(x,y); 39 } 40 dp(0,m); 41 printf("%d ",f[0][m]); 42 return 0; 43 }