트 리 백 팩 DP 의 두 가지 최적화 방식 - vijos 1676, codeforces 815 c

1. O (nm) - vijos 1676 도자기 로 사 과 를 먹는다.
배경 도 자 기 는 사 과 를 즐겨 먹는다.
curimit 를 묘사 하면 도자기 가 사 과 를 좋아 한 다 는 것 을 안다.그래서 curimit 는 도자기 생일 때 그 에 게 사과 나 무 를 주 려 고 한다.
curimit 는 생일 선물 로 이런 사과 나 무 를 준비 했다. 이 사과 나 무 는 n 개의 노드 가 있 고 각 노드 에 c [i] 개의 사과 가 있 으 며 이 나 무 는 높이 가 h 이다.
그러나 curimit 가 이 나 무 를 도도 에 게 보 여 주 었 을 때 도 도 도 는 "올해 생일 에는 선물 을 받 지 않 고 선물 을 받 을 때 절 포인트 만 받 고 높이 가 k 를 초과 하지 않 는 사과 나무" 라 고 말 했다. 이번 에는 curimit 가 어려움 을 겪 었 다. curimit 가 보 낸 나 뭇 가 지 는 잎 이 무성 하고 노드 수 - 높이 ≤ k 를 만족 시 키 지 못 한다.그래서 curimit 는 나 뭇 가 지 를 잘라 서 다 듬 은 나 무 를 노드 수 - 높이 ≤ k 에 만족 시 키 기로 결 정 했 습 니 다. 그러나 curimit 는 가능 한 한 많은 사과 수 를 유지 하고 싶 습 니 다.curimit 는 그 에 게 다 듬 은 나무 가 최대 몇 개의 사 과 를 보존 할 수 있 는 지 계산 해 달라 고 부탁 하고 싶 습 니 다.
주: 하나, 노드 1 은 나무 뿌리 이 므 로 잘 라 낼 수 없습니다.
2. 1 개의 노드 의 나무 높이 는 1 이다.
한 과목 의 가지치기 가 조건 을 만족 시 키 는 나무 에 대해 나무의 size 가 가장 큰 것 은 m + 나무의 가장 긴 체인 이다. 다시 말 하면 m 개의 결점 + 하나의 체인 을 취하 여 수익 을 어떻게 최대 화 하 는 지 하 는 동시에 나무 가방 dp 의 부모 노드 를 선택해 야 서브 노드 를 선택 할 수 있 는 조건 도 만족 시 켜 야 한다.쉽게 알 수 있 듯 이 선택 한 체인 이 길 수록 좋 기 때문에 답 에 포 함 된 가장 긴 체인 은 반드시 잎 이 맺 힌 곳 을 따라 갈 것 이다.논문 에서 의 상태 설정 방식 을 사용 하면 dp [u] [i] 는 u 노드 왼쪽 의 모든 노드 와 모든 하위 노드 를 고려 하여 i 가 얻 을 수 있 는 최대 수익 을 소비 했다 고 밝 혔 다.그러면 임의의 잎 노드 v, dp [v] [i] 는 v 결점 왼쪽 결점 에서 i 를 소비 하 는 최대 수익 을 나타 낸다. 왼쪽 에서 오른쪽 dfs 를 한 번 더 오른쪽 에서 왼쪽 dfs 를 한 번 더 얻 고 두 개의 dp 배열 을 얻 으 면 잎 노드 와 왼쪽 의 비용 을 매 거 져 답 을 얻 을 수 있다.

#include

using namespace std;
typedef long long ll;
const int maxn=4005;
const int maxm=505;
const int maxe=maxn*2;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
int n,m,k;
int dpl[maxn][maxm];
int dpr[maxn][maxm];
int c[maxn];
vector<int> e[maxn];
int sum[maxn];
int a,b;
int ans;

void dfsl(int u,int fa){
    for(int i=0;iint v=e[u][i];
        if(v==fa)continue;
        sum[v]=sum[u]+c[v];
        for(int i=0;i<=k;i++)dpl[v][i]=dpl[u][i];
        dfsl(v,u);
        for(int i=1;i<=k;i++){
            dpl[u][i]=max(dpl[u][i],dpl[v][i-1]+c[v]);
        }
    }
}

void dfsr(int u,int fa){
    bool leaf=1;
    for(int i=e[u].size()-1;i>=0;i--){
        int v=e[u][i];
        if(v==fa)continue;
        leaf=0;
        for(int i=0;i<=k;i++)dpr[v][i]=dpr[u][i];
        dfsr(v,u);
        for(int i=1;i<=k;i++){
            dpr[u][i]=max(dpr[u][i],dpr[v][i-1]+c[v]);
        }
    }
    if(leaf){
        for(int i=0;i<=k;i++){
            ans=max(ans,dpl[u][i]+dpr[u][k-i]+sum[u]);
        }

    }
}

int main(){
    scanf("%d%d",&n,&k);
    scanf("%d%d",&a,&c[1]);
    for(int i=2;i<=n;i++){
        scanf("%d%d",&a,&c[i]);
        e[a].push_back(i);
        e[i].push_back(a);
    }
    sum[1]=c[1];
    dfsl(1,0);
    dfsr(1,0);
    printf("%d
",ans);
    return 0;
}

2.O(n^2)——codeforces 815C - Karen and Supermarket
슈퍼마켓 에서 물건 을 사면 물건 마다 원가 와 쿠폰 을 사용 하면 줄 일 수 있 는 비용 이 있다.그러나 쿠폰 은 사전 사용 조건 이 있 습 니 다. 쿠폰 i 를 사용 하려 면 쿠폰 xi (나무 가방 dp 의 조건) 를 사용 해 야 합 니 다. 최대 얼마 까지 살 수 있 는 지 예산 b 를 초과 하지 않 을 수 있 는 지 물 어보 세 요.
b 의 범 위 는 1e9 로 상 태 를 설정 할 수 없습니다. dp [i] [j] [k] 는 i 를 루트 노드 로 하여 사용 하지 않 고 j 개 물품 을 사 는 데 가장 필요 한 비용 을 표시 합 니 다.
최 적 화 된 방식 은 이전 할 때 size 배열 을 이용 하여 매 거 횟수 를 줄 이 고 매 거 횟수 를 합 법 적 인 점 대수 n ^ 2 로 만 드 는 것 이다.

#include

using namespace std;
typedef long long ll;
const int maxn=5005;
const int maxm=505;
const int maxe=maxn*2;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
int n,m,k,a;
int dp[maxn][maxn][2];
vector<int> e[maxn];
int c[maxn],d[maxn];
int siz[maxn];

int dfs(int u,int fa){
    dp[u][0][0]=0;
    dp[u][1][0]=c[u];
    dp[u][1][1]=c[u]-d[u];
    siz[u]=1;
    for(int i=0;iint v=e[u][i];
        if(v==fa)continue;
        dfs(v,u);
        for(int i=siz[u];i>=0;i--){
        //for(int i=0;i<=siz[u];i++){
            for(int j=1;j<=siz[v];j++){
                dp[u][i+j][0]=min(dp[u][i+j][0],dp[u][i][0]+dp[v][j][0]);
            }
        }
        for(int i=siz[u];i>=0;i--){
        //for(int i=1;i<=siz[u];i++){
            for(int j=1;j<=siz[v];j++){
                dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][1]+min(dp[v][j][1],dp[v][j][0]));
            }
        }
        siz[u]+=siz[v];
    }
}

int main(){
    scanf("%d%d",&n,&m);
    scanf("%d%d",&c[1],&d[1]);
    for(int i=2;i<=n;i++){
        scanf("%d%d%d",&c[i],&d[i],&a);
        e[a].push_back(i);
        e[i].push_back(a);
    }
    memset(dp,0x3f,sizeof(dp));
    dfs(1,0);
    for(int i=n;i>=0;i--){
        if(dp[1][i][0]<=m||dp[1][i][1]<=m){
            printf("%d",i);
            break;
        }
    }
    return 0;
}