月度归档：2009年09月

选课(Tree dynamic)

发表回复

问题描述
学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。 　　在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，…。 例如:表中1是2的先修课，2是3、4的先修课。如果要选3，那么1和2都一定已被选修过。 你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。 输入格式 Input Format
输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。

以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。

输出格式 Output Format
输出文件只有一个数,实际所选课程的学分总数。

样例输入 Sample Input
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

样例输出 Sample Output
13

注释 Hint

算法分析
典型树型DP

有两种方法:
1.构建一颗多叉树,父结点选了才能选子结点,递归调用和指针.
2.将多叉树转化为2叉树(左儿子右兄弟),左儿子必须要有父结点而右儿子不必,递归调用和数组记录.
这里讲第一种:
f[i,j]表示第i个结点为根最多选j个课时得到的最大学分.
初值f[i,j]:=score[i];

对于一个父结点x,它有num个子结点,为son[i].用类似背包的方式处理子结点的加分.则
f[x,j]:=max{f[x,j],f[x,k]+f[son[i],j-k]} 2<=j<=m,0<=i<=num;1<=k<=j 注意对于一开始的输入m应该加1,因为需要设置一个根为0　　 树型DP。 将N叉树转化成二叉树，在建树过程中就将其转化。 tree[i,j]=max{tree[tree[i].right,j],tree[tree[i].left,k-1]+tree[tree[i].right,y-k]+tree[i].data} 　　 {0<=i<=n,2<=j<=m,1<=k<=j} 原本是多叉树，将它转变成二叉树。如果两节点a,b同为兄弟，则将b设为a的右节点；如果节点b是节点a的儿子，则将节点b设为a的左节点。 【代码】 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <stdio.h>
#include <string.h>
 
#define MAXN 501
typedef struct node
{
       int mark;
       int l, r;
}tree;
 
tree a[MAXN];
int f[MAXN][MAXN], lastkid[MAXN];
void dp(int i, int j);
int main()
{
       int n, m, i, pre;
       scanf("%d%d", &n, &m);
       memset(a, 0, sizeof(a));
       memset(lastkid, 0, sizeof(lastkid));
 
       for (i = 0; i <= n; i++)
       {
              a[i].l = a[i].r = a[i].mark = 0;
              lastkid[i] = 0;
       }
 
       for (i = 1; i <= n; i++)
       {
              scanf("%d%d", &pre, &a[i].mark);
              if (lastkid[pre] == 0)     //没有兄弟结点,则成为pre的左子树
              {
                     lastkid[pre] = i;
                     a[pre].l = i; 
              }
              else                              //有兄弟结点,成为兄弟结点的右子树
              {
                     a[lastkid[pre]].r = i;
                     lastkid[pre] = i;
              }
       }
 
       for (i = 1; i <= m; i++)  
              dp(a[0].l, i);
 
       printf("%d\n", f[a[0].l][m]);
       return 0;
 
}
 
void dp(int i, int j)
{
       int k;
       if (a[i].l != 0) dp(a[i].l, j);    //切记,一定要先求其孩子的
       if (a[i].r != 0) dp(a[i].r, j);
       f[i][j] = a[i].mark; 
       if (a[i].l != 0 || a[i].r != 0)
       {
              for (k = 1; k <= j; k++)
                     if (f[i][j] < (f[a[i].l][k - 1] + f[a[i].r][j - k] + a[i].mark))
                            f[i][j] = f[a[i].l][k - 1] + f[a[i].r][j - k] + a[i].mark;
       }
 
       if (f[i][j] < f[a[i].r][j])
              f[i][j] = f[a[i].r][j];
}

战略游戏(Tree dynamic)

发表回复

问题描述
Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。
　　请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。

Input
输入文件中数据表示一棵树，描述如下：
　　第一行 N，表示树中结点的数目。
　　第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，…，rk。
　　对于一个n(0 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。 Output

输出文件仅包含一个数，为所求的最少的士兵数目。

Sample Input
4
0 1 1
1 2 2 3
2 0
3 0

Sample Output
1

算法分析
树型DP

首先建树，得到根结点。设置数组F[N][2]，f[x][1]表示要看守住以x为根的子树中所有边，x处有士兵时需要的最少士兵数，f[x][0] 表示要看守住以x为根的子树中所有边，x处无士兵时需要的最少士兵数。自下而上地计算每个结点的两种值：一个结点的有士兵的值等于它所有子树的有士兵的值与没有士兵的值的较小值之和再加1；一个结点没有士兵的值等于它所有子树的有士兵的值之和。根结点有士兵的值和没有士兵的值中的较小值即为答案。

【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <stdio.h>
#include <string.h>
#define min(a,b) a<b?a:b
typedef struct
{
       int num;
       int child[1501];
}node;     //树型结构
node a[1501];
int f[1501][2];       
int n;
 
void dp(int root)
{
       int i;
       if (a[root].num == 0)
       {
              f[root][1] = 1;
              f[root][0] = 0;
              return;
       }
 
       f[root][1] = 1;
       f[root][0] = 0;
 
       for (i = 0; i < a[root].num; i++)
       {
              dp(a[root].child[i]);       //先dp再相加 从下往上
              f[root][1] += min(f[a[root].child[i]][1], f[a[root].child[i]][0]);
              f[root][0] += f[a[root].child[i]][1];
       }
}
 
int main()
{
       int i, j, k, r, root;
       scanf("%d", &n);
       r = 0;
       root = 0;
       for (i = 0; i < n; i++)
       {
              scanf("%d", &k);
              r += k;
              scanf("%d", &a[k].num);
 
              for (j = 0; j < a[k].num; j++)
              {
                     scanf("%d", &a[k].child[j]);
                     root += a[k].child[j];
              }
       }
       root = r - root;       //求根结点
       memset(f, 0, sizeof(f));
       dp(root);
       printf("%d\n", min(f[root][1], f[root][0]));
       return 0;
}

小胖守皇宫（Tree dynamic）

2条回复

问题描述
huyichen世子事件后，xuzhenyi成了皇上特聘的御前一品侍卫。

皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。
可是xuzhenyi手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
帮助xuzhenyi布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

输入格式 Input Format

输入文件中数据表示一棵树，描述如下：
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0 对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。
输出格式 Output Format
输出文件仅包含一个数，为所求的最少的经费。

样例输入 Sample Input
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

样例输出 Sample Output

25

注释 Hint

如图

算法分析
树型动态规划
本题既可以用有向树来做,也可以用无向图随机选根结点

分析可见,对于当前结点i,它有num个子结点,它有它有3种状态:

1:在当前位放置守卫的情况(被自己所控制)
2:不在当前位放置守卫,但是它已经被它的子结点所控制
3:不在当前位放置守卫,它还没有被它的子结点所影响(即被其父结点控制)

用f[i,x]表示结点i的第x种情况:

1情况的值由其子结点的1,2,3情况得到最优
2情况的值由其子结点的1,2情况得到最优
3情况的值只可由其2情况求和.

第2种情况要特别注意,要求它的子结点中必须有一个是1状况的,所以可以先将最小值求和,
然后加上这num个子结点中每个的1情况与最优情况的f值之差–most

方程:
f[i,1]:=Σ(min{f[son[j],1],f[son[j],2],f[son[j],3]})+a[i]
f[i,2]:=Σ(min{f[son[j],1],f[son[j],2]})+most
f[i,3]:=Σ(f[son[j],2]),　　　　　　　　　　 1<=j<=num

还有要注意的一点就是对于极限数据,树被拉成了一条链.
有向图解法如果每次递归都开一个数组那么内存会爆,对此,可以不用数组记录子结点,而直接用链表就
可以大大节约空间了.甚至把数组改成全局变量也是可行的,就是注意递归调用要在DP之前.

【代码】

#include 
#define MAXN 1501
#define MAXINT 2000000000
typedef struct
{
        int v, num;
        int child[MAXN];
}node;
 
node a[MAXN];
int f[MAXN][4];
int min2(int x, int y)
{
       return x