한권통-가산점 두 갈래 나무+분리와 합체(구간 DP+기록 방안)

플러스 트리 원제 링크

제목은 n개의 노드를 설정한 두 갈래 트리의 중순은 (1,2,3,..., n)이고 그 중에서 숫자는 1,2,3,..., n은 노드 번호이다.
각 노드에는 하나의 점수(모두 정수)가 있고 i번째 노드의 점수는 di,tree와 그의 모든 나무는 하나의 가산점이 있으며 하나의 나무subtree(tree 자체도 포함)의 가산점 계산 방법은 다음과 같다.
subtree의 왼쪽 나무의 가산점× subtree의 오른쪽 나무의 가산점
만약 어떤 하위 나무가 비어 있다면, 그 가산점을 1로 규정한다.잎의 가산점은 잎 노드 자체의 점수로 그것의 빈자나무를 고려하지 않는다.
중서열(1,2,3,..., n)에 부합되고 가산점이 가장 높은 두 갈래 나무tree를 구해 보세요.
출력 요구:
(1)tree의 최고 가산점
(2)tree의 앞 순서 반복
형식 첫 번째 줄 입력: 노드 개수인 정수 n.
두 번째 줄: n개의 공백으로 구분된 정수, 각 노드의 점수(0
출력 형식 첫 번째 줄: 최대 가산점을 주는 정수(결과는 400000000을 초과하지 않음).
두 번째 줄: n개의 공백으로 구분된 정수로 이 나무의 앞을 훑어봅니다.여러 가지 방안이 존재하면 사전 순서가 가장 작은 방안을 출력합니다.
데이터 범위 n<30 입력 샘플: 557 1 2 10 출력 샘플: 145 3 1 2 4 5 사고방식: 사실 저는 이 문제(소성 bb)를 잘 몰라요. 먼저 나무의 앞뒤가 훑어보는 등 전송문이 먼저 첫 번째 문제를 해결하고 나무의 최대 가산점을 어떻게 계산하는지 봅시다.우리는 dp[i][j]를 설정하여 모든 중서열이 [i, j] 단락의 가산점이 가장 큰 나무임을 나타낸다. 뿌리 노드가 있는 위치를 일일이 열거하여 상태 이동을 할 수 있다.

	for(int k=l;k<r;k++){
         int left=1,right=1;
         if(k!=l) left=dp[l][k-1];/// 
         if(r!=k) right=dp[k+1][r];// 
         dp[l][r]=max(dp[l][r],left*right+a[k]);
    }

마지막 최대 가산점은 dp[1][n]입니다. 방안을 어떻게 출력하는지 다시 한 번 봅시다.또한 앞의 출력은 루트 노드를 먼저 출력하고 좌우 트리를 출력하기 때문에 우리는 이 특성을 이용하여 방안의 출력을 할 수 있다.
코드:

#include
using namespace std;
const int maxn=35;
int a[maxn];
int dp[maxn][maxn];/// i~j 
int pre[maxn][maxn];//pre[i][j] [i,j] 
int n;
void dfs(int l,int r){
    if(l>r) return ;
    int x=pre[l][r];// 
    cout<<x<<" ";
    dfs(l,x-1);// 
    dfs(x+1,r);/// 
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    
    for(int len=1;len<=n;len++)
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            if(l==r) dp[l][r]=a[l],pre[l][r]=l;// 
            else{
                for(int k=l;k<r;k++){
                    int left=1,right=1;
                    if(k!=l) left=dp[l][k-1];/// 
                    if(r!=k) right=dp[k+1][r];// 
                   //dp[l][r]=max(dp[l][r],left*right+a[k]);
                   if(dp[l][r]<left*right+a[k]){
                       dp[l][r]=left*right+a[k];
                       pre[l][r]=k;
                   }
                }
                
            }
        }
    cout<<dp[1][n]<<endl;
    dfs(1,n);
    return 0;
}

유사한 문제:

분리와 합체 원제 링크

기계실에서 수일 동안의 교섭을 통해 LYD는 두신소로부터 분리와 합체를 배웠다. 관문을 통과하기 전에 두신소는 그에게 테스트를 주었다. 두신소는 n개의 구역을 만들었다. 그들은 바로 옆에 줄을 서서 번호 1...n을 매겼다.각 구역에 OI계의 금 열쇠가 놓여 있는데, 하나하나가 모두 일정한 가치가 있으니, LYD는 당연히 그들을 얻고 싶어한다.그러나 두신우는 LYD가 한꺼번에 그들을 모두 가져갈 수 없고 매번 한 자루만 가져갈 수 있다고 규정했다.가능한 한 빨리 모든 금 열쇠를 얻기 위해 LYD는 자연히 방금 배운 분리와 합체 기술을 사용했다.처음에 LYD는 1...n-1 중 어느 구역을 선택해서 들어갈 수 있습니다. 이 구역을 k로 적어도 괜찮습니다.들어간 후 LYD는 k구역에서 분리되어 두 개의 작은 LYD로 분리된다.분리가 완료되는 동시에 한쪽 벽이 k구역과 k+1구역 사이에 올라가서 1...k와 k+1...n을 두 개의 독립된 구간으로 차단하고 각 구간 내에서 구간 끝(즉 1...k-1과 k+1...n-1에서 선택)을 제외한 임의의 구역에서 다시 분리한다. 이렇게 하면 네 개의 작은 LYD가 있다...상기 서술한 분리를 반복하여 각 작은 LYD가 자신이 있는 구간이 한 구역만 남았다는 것을 발견할 때까지그러면 그들은 자신이 꿈꾸던 OI금 열쇠를 안을 수 있다.그러나 LYD는 이렇게 많은 개체로 나누어 세상에 존재할 수 없다. 이런 작은 LYD는 다시 합체하고 합체의 작은 LYD가 있는 구간 중간의 벽은 사라진다.합체는 획득됩니다(합병 후 해당 구간 좌우 끝 구역에서 금 열쇠의 가치의 합)\times()×(이전에 분리되었을 때 있던 지역의 금 열쇠 가치).예를 들어 LYD는 1...3구간 중 2번 구역을 1...2와 3...3 두 구간으로 분리한 적이 있는데 통합할 때 얻는 가치는 (1번 금열쇠 가치+3번 금열쇠 가치)\times()×(2번 금 열쇠의 가치).LYD는 최종적으로 얻을 수 있는 최대 총 가치를 프로그래밍하여 분리 단계의 앞뒤로 구역이 왼쪽에서 오른쪽으로 순서대로 출력하여 분리 구역 번호를 발생시킵니다.여러 가지 방안이 있다면 분리 구역을 최대한 왼쪽으로 하는 방안을 선택하십시오. (출력 사전의 순서가 가장 작은 것으로 이해할 수도 있습니다.)예를 들어 먼저 두 개의 구역을 인쇄한 다음에 왼쪽에서 오른쪽으로 두 개의 분리된 구역을 인쇄한 다음에 네 개의 분리된 구역을 인쇄한다... 설명을 입력하십시오: 첫 번째 줄은 정수 n 두 번째 줄은 공백으로 분리된 정수 a_ii, 1...n 구역에 있는 모든 금 열쇠의 가치를 표시합니다.출력 설명: 첫 번째 줄은 하나의 수로 얻은 최대 가치를 나타낸다. 두 번째 줄은 분리 단계의 앞뒤로 구역이 왼쪽에서 오른쪽으로 순서대로 출력에 분리 구역 번호가 발생한다.여러 가지 방안이 있다면 분리 구역을 최대한 왼쪽으로 하는 방안을 선택하십시오. (출력 사전의 순서가 가장 작은 것으로 이해할 수도 있습니다.)예시 1 입력 복사 7 1 2 3 4 5 6 7 출력 복사 238 1 2 3 4 5 6 비고: 20%20% 의 데이터에 대해 n\leq 10n ≤10;40%40%의 데이터에 대해 n\leq50n≤50;100%100%의 데이터에 대해 n, a_i\leq300n, ai≤300, 연산 과정과 결과가 32비트 정수 범위를 초과하지 않도록 보증합니다.
제목: (제목이 길어서 짜증나) 위와 대체적으로 비슷하지만 가산점을 주는 방식이 바뀌었다.
LYD는 1...3구간 중 2번 구역에서 1...2와 3...3 두 구간으로 분리되었는데, 통합할 때 얻는 가치는 (1번 금열쇠 가치+3번 금열쇠 가치)\times()×(2번 금 열쇠의 가치).
코드:

#include
using namespace std;
const int maxn=1100;
int a[maxn];
int dp[maxn][maxn];
int pre[maxn][maxn];
int n,k,t;
void dfs(int u,int l,int r){
    if(l>=r) return ;
    int x=pre[l][r];
    if(u==k){
        cout<<x<<" ";
        t=1;
        return ;
    }
    dfs(u+1,l,x);dfs(u+1,x+1,r);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int len=1;len<n;len++)
        for(int l=1;l+len<=n;l++){
            int r=l+len;
            for(int k=l;k<r;k++){
                int left=0,right=0;
                left=dp[l][k];
                right=dp[k+1][r];
                   
                if(dp[l][r]<(left+right)+(a[l]+a[r])*a[k]){
                    dp[l][r]=(left+right)+(a[l]+a[r])*a[k];
                    pre[l][r]=k;
                }
            }
        }
    cout<<dp[1][n]<<endl;
    t=1;
    while(t){
        t=0;
        k++;
        dfs(1,1,n);
    }
    return 0;
}

참고 문헌: 전송문