树状DP

时间：2022-05-10 06:40:20

紫皮，各种，非原创

树状数组在我的理解就是在决策过程中具有层次关系，像是树一样，具有上下级关系或者上级对上级一定程度的限制条件

uva 12186

工人的请愿书

下属中不小于 T% 的人签字时会签字递给上级，问至少需要多少人签字才能传给老板

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <map>

#include <queue>

#include <vector>

const int MAXN = + ;

const double ESP = 10e-;

const double Pi = atan(1.0) * ;

const int INF = 0xffffff;

const int MOD = ;

typedef long long LL;

using namespace std;

vector<int>sons[MAXN];

int n,T;

int dp(int u){

    if(sons[u].empty()){

        return ;

    }

    int k = sons[u].size();

    vector<int>d;

    for(int i = ;i < k;i++){

        d.push_back(dp(sons[u][i]));

    }

    sort(d.begin(),d.end());

    int c = (k*T - ) / + ;

    int ans = ;

    for(int i = ;i < c;i++){

        ans += d[i];

    }

    return ans;

}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d%d",&n,&T)){

        if(!n && !T){

            break;

        }

        for(int i = ;i <= n;i++){

            sons[i].clear();

        }

        for(int i = ;i <= n;i++){

            int a;

            scanf("%d",&a);

            sons[a].push_back(i);

        }

        printf("%d\n",dp());

    }

    return ;

}

poj 3442 / uva 1220 Party at Hali-Bula

晚会邀请人，但是上下级不能在一起，求最多能邀请多少人，并且方案是否唯一

d(u,1) 邀请了u，所以其下级不能邀请 所以d(u,1) = sum(d(v,0) );

d(u,0) 没有邀请u,所以其下级，可以邀请也可以不邀请 则 d(u,0) = sum{ max( d(v,0),d(v,1) ) };

f(u,0) 为 1表示不唯一，否则唯一

f(u,1) 表示邀请了u，其方案是否唯一，当f(v,0)不唯一时，则f(u,1)必须不唯一

f(u,0) 没邀请 u 的方案是否唯一，如果 d(v,1) == d(v,0) 或者 由其所取的值得f(v)决定

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <stack>

#include <cctype>

#include <string>

#include <queue>

#include <map>

#include <set>

using namespace std;

const int INF = 0xffffff;

const double ESP = 10e-;

const double Pi =  * atan(1.0);

const int MAXN =   + ;

const long long MOD =  ;

const int dr[] = {,,-,,-,,-,};

const int dc[] = {,,,-,,-,-,};

typedef long long LL;

LL gac(LL a,LL b){

   return b?gac(b,a%b):a;

}

int n;

int d[MAXN][];

int child[MAXN];

bool f[MAXN][];

int cnt;

map<string,int>m;

vector<int>G[MAXN];

int getNum(string str){

    int a;

    if(m.count(str)){

        a = m[str];

    }

    else{

        a = cnt;

        m[str] = cnt++;

    }

    return a;

}

void dp(int r){

    if(!G[r].size()){ //没有孩子

        d[r][] = ;//如果选择r能获得的最大值

        d[r][] = ; //如果不选择r获得的最大值

//        f[r][1] = 1;

//        f[r][0] = 1;

        return;

    }

    d[r][] = ; //如果选择了r则包含r这个员工

    bool flag = ;

//    f[r][0] = 1;

    int len = G[r].size();

    for(int l = ;l < len;l++){

        dp(G[r][l]);

        int i = G[r][l];

        if(f[i][]){

            f[r][] = ;

        }

        d[r][] += d[i][];

        if(d[i][] > d[i][]){

            d[r][] += d[i][];

            if(f[i][])

                f[r][] = ;

        }

        else{

            d[r][] += d[i][];

            if(d[i][] == d[i][] || f[i][])

                f[r][] = ;

        }

//        if(G[r][i]){

//            dp(i);

//            if(f[i][0]){

//                f[r][1] = 1;

//            }

//            d[r][1] += d[i][0];

//            if(d[i][0] > d[i][1]){

//                d[r][0] += d[i][0];

//                if(f[i][0])

//                    f[r][0] = 1;

//            }

//            else{

//                d[r][0] += d[i][1];

//                if(d[i][1] == d[i][0] || f[i][1])

//                    f[r][0] = 1;

//            }

////            d[r][1] += d[i][0]; //如果选择了r这其下级不能选择

////            if(!f[i][0]){

////                flag = 0;

////            }

////            if(d[i][0] == d[i][1]){

////                f[i][0] = 0;

////                d[r][0] += d[i][0];

////            }

////            else if(d[i][0] > d[i][1]){

////                d[r][0] += d[i][0];

////                if(!f[i][0]){

////                    f[r][0] = 0;

////                }

////            }

////            else{

////                d[r][0] += d[i][1];

////                if(!f[i][1]){

////                    f[r][0] = 0;

////                }

////            }

//

//        }

//    }

//    if(flag){

//        f[r][1] = 1;

    }

    return;

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("inpt.txt","r",stdin);

   // freopen("output.txt","w",stdout);

#endif

    while(~scanf("%d",&n) && n){

        cnt = ;

        memset(child,,sizeof(child));

        memset(f,,sizeof(f));

        memset(d,,sizeof(d));

        string str1;

        string str2;

        m.clear();

        cin >> str1;

        m[str1] = cnt++;

        int a,b;

        for(int i = ;i <= n;i++){

            G[i].clear();

        }

        for(int i = ;i < n;i++){

            cin >> str1 >> str2;

            a = getNum(str1);

            b = getNum(str2);

            G[b].push_back(a);

        }

        dp();

        if(d[][] == d[][]){

            printf("%d No\n",d[][]);

        }

        else if(d[][] > d[][]){

            printf("%d %s\n",d[][],!f[][]?"Yes":"No");

        }

        else{

            printf("%d %s\n",d[][],!f[][]?"Yes":"No");

        }

    }

    return ;

}

poj 3398 Perfect Service / uva 1218

联通的计算机，从中间抽取几台电脑充当服务器，使每台电脑恰好有一台服务器相连，求最小的服务器数目

d(u,0) u是服务器，其子节点既可以是服务器，也可以不是服务器

d(u,1) u 不是服务器，但是其父亲是服务器,其儿子一定不是服务器

d(u,2) u不是服务器，其父亲也不是服务器,u恰好一个v是服务器

d(u,0) = sum{min(d(v,0),d(v,1)) } + 1;

d(u,1) = sum{d(v,2)};

d(u,2) = sum{d(vv,2)} = min(d(u,1)- d(v,2) + d(v,0)) //其某一个子节点为服务器

因为是无向树所以需要vis标记

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <algorithm>

#include <vector>

const int MAXN =  + ;

const int INF = 0xffffff;

const int mod = ;

const double Pi = atan(1.0)*;

const double ESP = 10e-;

using namespace std;

vector<int>G[MAXN];

int d[MAXN][];

bool vis[MAXN];

int n;

void dp(int u){

    vis[u] = ;

    int len = G[u].size();

    d[u][] = ;  //u是服务器，其子节点既可以是服务器，也可以不是，其父节点可以是服务器，也可以不是

    d[u][] = ; //u不是服务器，但是u父亲是服务器，所以其子节点都不是服务器

    d[u][] = INF; // u，和u的父亲都不是服务器，所以u的子节点必须有点是服务器

    vector<int>arr;

    for(int i = ;i < len;i++){

        int v = G[u][i];

        if(vis[v])

            continue;

        dp(v);

        arr.push_back(v);

        d[u][] += min(d[v][],d[v][]);  // 子节点既可以是服务器又可以不是服务器所以取最小值

        d[u][] += d[v][]; // u不是服务器，子节点不是服务器，所以等于d[v][2]父亲和其本身都不是服务器的相加

    }

    len = arr.size();

    for(int i = ;i < len;i++){

        int v = arr[i];

        d[u][] = min(d[u][],d[u][] - d[v][] + d[v][]);

    }

}

int main(){

   // freopen("input.txt","r",stdin);

    while(~scanf("%d",&n)){

        for(int i = ;i <= n;i++){

            G[i].clear();

        }

        memset(vis,,sizeof(vis));

        memset(d,,sizeof(d));

        for(int i = ;i < n;i++){

            int a,b;

            scanf("%d%d",&a,&b);

            G[b].push_back(a);

            G[a].push_back(b);

        }

        dp();

        int ans = INF;

        ans = min(d[][],d[][]);

        printf("%d\n",ans);

        scanf("%d",&n);

        if(n < )

            break;

    }

    return ;

}

相关文章