【CodeVS1486】愚蠢的矿工

Description

Stupid 家族得知在HYC家的后花园里的中央花坛处,向北走3步,向西走3步,再向北走3步,向东走3步,再向北走6步,向东走3步,向南走12步,再向西走2步( - -||)就能找到宝藏的入口,而且宝藏都是藏在山里的,必须挖出来,于是Stupid家族派狗狗带领矿工队去挖宝藏.(HYC家的宝藏被狗狗挖走后有什么感想?)

这个宝藏的制造者为了掩盖世人耳目,他做的宝藏是没有出口,只有入口,不少建造宝藏的人都死在里面.现在知道宝藏总共有N个分岔口,在分岔口处是有财宝的,每个宝藏点都有一个财富值.狗狗只带了M个人来,而且为了安全起见,在每个分岔口,必须至少留一个人下来,这个留下来的人可以挖宝藏(每个人只能挖一个地方的宝藏),这样才能保证不会迷路,而且这个迷宫有个特点,任意两点间有且只有一条路可通.狗狗为了让他的00开心,决定要尽可能地多挖些宝藏回去.现在狗狗的圈叉电脑不在身旁,只能求救于你了,你要知道,狗狗的终身幸福就在你手上了..（狗狗ps：00，你不能就这样抛弃偶……）

Input

第1行：两个正整数N,M .N表示宝藏点的个数,M表示狗狗带去的人数(那是一条懒狗,他自己可不做事)。(m<=100)

第2行：N个整数,第i个整数表示第i个宝藏的财富值.(保证|wi|<maxint)

第N+2行：两个非负整数A和B，表示A通向B,当A=0,表示A是入口.（保证A,B<=n）

Output

输出狗狗能带回去的宝藏的价值。

Sample Input

4 3

5 6 2 4

1 2

0 1

2 3

3 4

Sample Output

HINT

对于10%的数据，n<10

对于100%的数据，n<=1000

题解

和选课一样

我竟然一次就过了编译！

#include<iostream>
#include<cstdio>
#define N 1010
#define M 110
using namespace std;
int v[N];
int son[N][2];
int f[N][M];
int n,m,x,y,flag;
int DP(int k,int x)
{
    if (x == 0 || (flag && k==0)) return 0;
    flag = 1;
    if (f[k][x]) return f[k][x];
    for (int i=1;i<=x;i++)
    {
        f[k][x] = max(f[k][x],v[k]+DP(son[k][0],i-1)+DP(son[k][1],x-i));
    }
    f[k][x] = max(f[k][x],DP(son[k][1],x));
    return f[k][x];
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&v[i]);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);// x->y
        if (son[x][0]==0)
            son[x][0] = y;
        else
        {
            int fa = son[x][0];
            while (son[fa][1])
                fa = son[fa][1];
            son[fa][1] = y;
        }
    }
    printf("%d",DP(0,m+1));
}