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;
        }
    }
}

좋은 웹페이지 즐겨찾기