POJ 2342 트리 dp

9985 단어 DP

제목:전송문

제목:

한 그루의 나무에 모든 결점마다 하나의 권한이 있는데 부모 노드와 하위 노드가 동시에 나타날 수 없다. 권한과 최대 값이 얼마인지 구한다.

문제 풀이:

우리는 나무 위에서 dp를 뛰어야 한다. 문제의 모형은 사용하거나 사용하지 않기 때문에 우리는 나무 위에서 01배낭의 그 모형을 뛰면 된다.

AC 코드:

#include
#include
#include
using namespace std;
int dp[6005][2],val[6005],index_v[6005],vis[6005];
vector<int>adj[6005];
void dfs(int u) {
    vis[u]=true;
    dp[u][0]=0;//      
    dp[u][1]=val[u];//     
    for(int i=0; i<adj[u].size(); i++) {
        int v=adj[u][i];
        if(vis[v])
            continue;
        dfs(v);
        dp[u][0]+=max(dp[v][0],dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}
int main(void) {
    int n,u,v;
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>val[i];
    }
    while(cin>>v>>u&&u+v) {
        adj[u].push_back(v);
        index_v[v]++;
    }
    for(int i=1; i<=n; i++) {
        if(!index_v[i]) {
            dfs(i);//dfs     
            cout<<max(dp[i][0],dp[i][1]);
            return 0;
        }
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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