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 }

좋은 웹페이지 즐겨찾기