Vijos 1100 플러스 두 갈래 트리(트리 DP)
9500 단어 두 갈래 나무
구간DP와 비슷한것 같기도 하고 간단한것 같기도 하고 1Y도 안되고 예전에는 생각이 없었는데...
1 #include <cstdio>
2 #include <cstring>
3 #include <queue>
4 #include <string>
5 using namespace std;
6 #define LL long long
7 int p[101];
8 int o[101];
9 LL dp[101][101];
10 int num = 1;
11 LL dfs(int L,int R)
12 {
13 int i;
14 LL temp;
15 LL maxz = -1000000;
16 if(dp[L][R])
17 return dp[L][R];
18 if(L > R)
19 return 1;
20 if(L == R)
21 return p[L];
22 for(i = L;i <= R;i ++)
23 {
24 if(maxz < (temp = dfs(L,i-1)*dfs(i+1,R)+p[i]))
25 {
26 maxz = temp;
27 }
28 }
29 dp[L][R] = maxz;
30 return dp[L][R];
31 }
32 void find(int L,int R)
33 {
34 int i,key;
35 if(L == R)
36 {
37 o[num++] = L;
38 return ;
39 }
40 else if(L > R)
41 return ;
42 for(i = L;i <= R;i ++)
43 {
44 if(dp[L][R] == dfs(L,i-1)*dfs(i+1,R)+p[i])
45 {
46 key = i;
47 break;
48 }
49 }
50 o[num++] = key;
51 find(L,key-1);
52 find(key+1,R);
53 }
54 int main()
55 {
56 int i,n;
57 scanf("%d",&n);
58 for(i = 1;i <= n;i ++)
59 scanf("%d",&p[i]);
60 printf("%lld
",dfs(1,n));
61 find(1,n);
62 for(i = 1;i <= n;i ++)
63 {
64 if(i == 1)
65 printf("%d",o[i]);
66 else
67 printf(" %d",o[i]);
68 }
69 printf("
");
70 return 0;
71 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.