낙곡[P1040] 가산점 두 갈래 나무

4925 단어 noip문제풀이
이 문제는 나무의 문제이지만 구간DP의 기본적인 사고방식이다. 주어진 구간은 나무의 중순으로 두루 훑어보기 때문에 우리는 좌우 단점을 매거한다. dp[i][j]는 i에서 j호 구간에 표시된 하위 나무의 최대 점수를 나타내고 옮길 때 뿌리 노드 k를 매거하면 전이 방정식이 있다.
if(dp[j][k-1]*dp[k+1][i]+num[k]>dp[j][i]){
    dp[j][i]=dp[j][k-1]*dp[k+1][i]+num[k];
    rt[j][i]=k;
}

제목은 또한 출력의 순서를 요구합니다. 이동할 때 루트 그룹을 업데이트하고 rt[i][j]는 i에서 j까지의 구간에 표시된 하위 트리의 점수가 가장 높을 때의 뿌리 노드를 표시합니다.dfs 출력하면 됩니다.제목 문제로 인해 본 문제는 AC가 되지 않았지만 사상은 여전히 참고할 수 있다.
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int init(){
    int rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fh=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return fh*rv;
}
long long n,dp[50][50],rt[50][50],num[50];
void dfs(int l,int r){
    if(l>r) return;
    if(l==r){
        printf("%d ",rt[l][r]);
        return;
    }
    printf("%d ",rt[l][r]);
    dfs(l,rt[l][r]-1);
    dfs(rt[l][r]+1,r);
}
int main(){
    freopen("in.txt","r",stdin);
    n=init();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++){
        num[i]=init();
        dp[i][i]=num[i];rt[i][i]=i;
    }
    for(int t=1;t<=n;t++){
        for(int j=1;j+t<=n;j++){
            int i=j+t;
            for(int k=j;k<=i;k++){
                if(dp[j][k-1]*dp[k+1][i]+num[k]>dp[j][i]){
                    dp[j][i]=dp[j][k-1]*dp[k+1][i]+num[k];
                    rt[j][i]=k;
                }
            }
        }
    }

    cout<1][n]<1,n);
    fclose(stdin);
    return 0;
}
[51nod 1201] [DP+사유] 정수 구분 [N을 여러 개의 서로 다른 정수의 합으로 나누어 구분수를 구한다]
C언어로 쉽게 풀어쓴 자료구조 4단원

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage