Vijos 1180 수강신청(트리 DP)
8275 단어 OS
문제풀이를 참고하여 만든 것은 나무에 있지 않으면 일반적인 2차원 DP일 것이다. 전 i과목에서 j과목을 선택하여 가장 큰 점수를 얻었지만 이 문제는 매 과목마다 먼저 과목을 배울 수 있기 때문에 나무를 세우고 나무에 귀속한다.호랑이 형과 어떻게 나무를 세우는지 토론했는데 두 갈래 나무가 아니기 때문에 매 과목마다 아이가 많을 수도 있어요. 원래 인접표를 쓰려고 했는데 귀찮은 것 같아서 돌아가면 어떻게 해야 할지 모르겠어요. 또 다른 방식은 왼쪽 아들과 오른쪽 형제의 방식이에요. 예전에는 사용하지 않고 찾아봤어요풀다 이렇게 나무 상태를 옮기는 것은 간단하다. URAL에서 만든 두 갈래 나무의 트리 DP와 차이가 많지 않다.시작할 때도 또 다른 생각이 있었다. 먼저 각 점을 다시 분리하고 번호를 매긴 다음에 점차적으로 미루는 형식으로 바꿀 수 있다는 것이 가능할지 모르겠다.
이것은 여전히 정태적인 방법으로 한 것이다...첫째, 이렇게 세워서 공부했어요...
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4 #include <math.h>
5 struct node
6 {
7 int left,right;
8 };
9 int max(int a,int b)
10 {
11 return a > b ? a:b;
12 }
13 struct node tree[301];
14 int map[301][301],p[301];
15 void insert(int son,int father)
16 {
17 int t;
18 if(!tree[father].left)
19 {
20 tree[father].left = son;
21 }
22 else
23 {
24 t = tree[father].left;
25 while(tree[t].right)
26 {
27 t = tree[t].right;
28 }
29 tree[t].right = son;
30 }
31 }
32 int dp(int x,int y)
33 {
34 int i;
35 if(map[x][y] > 0)
36 return map[x][y];
37 if(x == 0||y == 0)
38 {
39 map[x][y] = 0;
40 return map[x][y];
41 }
42 map[x][y] = dp(tree[x].right,y);
43 for(i = 0;i <= y-1;i ++)// 0 ， ， 。。
44 {
45 map[x][y] = max(map[x][y],dp(tree[x].left,i)+dp(tree[x].right,y-i-1)+p[x]);
46 }
47 return map[x][y];
48 }
49 int main()
50 {
51 int n,m,i,fa;
52 scanf("%d%d",&n,&m);
53 for(i = 1;i <= n;i ++)
54 {
55 scanf("%d%d",&fa,&p[i]);
56 insert(i,fa);
57 }
58 printf("%d
",dp(tree[0].left,m));
59 return 0;
60 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[OS] 21. Beyond Physical Memory: MechanismsOS는 Page fault가 발생함에 따라 Page fault handler에 정의된대로 이를 처리(swap in)하는데, 이는 Page table에 해당 페이지가 swap 공간의 어느 위치에 저장되어 있는지 저장해...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
