紫皮，各种，非原创
树状数组在我的理解就是在决策过程中具有层次关系，像是树一样，具有上下级关系或者上级对上级一定程度的限制条件
uva 12186
工人的请愿书
下属中不小于 T% 的人签字时会签字递给上级，问至少需要多少人签字才能传给老板
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <vector> const int MAXN = 100000+ 10; const double ESP = 10e-8; const double Pi = atan(1.0) * 4; const int INF = 0xffffff; const int MOD = 2012; typedef long long LL; using namespace std; vector<int>sons[MAXN]; int n,T; int dp(int u){ if(sons[u].empty()){ return 1; } int k = sons[u].size(); vector<int>d; for(int i = 0;i < k;i++){ d.push_back(dp(sons[u][i])); } sort(d.begin(),d.end()); int c = (k*T - 1) / 100+ 1; int ans = 0; for(int i = 0;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 = 0;i <= n;i++){ sons[i].clear(); } for(int i = 1;i <= n;i++){ int a; scanf("%d",&a); sons[a].push_back(i); } printf("%d ",dp(0)); } return 0; }
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-8; const double Pi = 4 * atan(1.0); const int MAXN = 200 + 10; const long long MOD = 1000000007; const int dr[] = {1,0,-1,0,-1,1,-1,1}; const int dc[] = {0,1,0,-1,1,-1,-1,1}; typedef long long LL; LL gac(LL a,LL b){ return b?gac(b,a%b):a; } int n; int d[MAXN][2]; int child[MAXN]; bool f[MAXN][2]; 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][1] = 1;//如果选择r能获得的最大值 d[r][0] = 0; //如果不选择r获得的最大值 // f[r][1] = 1; // f[r][0] = 1; return; } d[r][1] = 1; //如果选择了r则包含r这个员工 bool flag = 1; // f[r][0] = 1; int len = G[r].size(); for(int l = 0;l < len;l++){ dp(G[r][l]); int i = G[r][l]; 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; } // 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 = 1; memset(child,0,sizeof(child)); memset(f,0,sizeof(f)); memset(d,0,sizeof(d)); string str1; string str2; m.clear(); cin >> str1; m[str1] = cnt++; int a,b; for(int i = 0;i <= n;i++){ G[i].clear(); } for(int i = 1;i < n;i++){ cin >> str1 >> str2; a = getNum(str1); b = getNum(str2); G[b].push_back(a); } dp(1); if(d[1][0] == d[1][1]){ printf("%d No ",d[1][0]); } else if(d[1][0] > d[1][1]){ printf("%d %s ",d[1][0],!f[1][0]?"Yes":"No"); } else{ printf("%d %s ",d[1][1],!f[1][1]?"Yes":"No"); } } return 0; }
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 = 10000 + 10; const int INF = 0xffffff; const int mod = 1000007; const double Pi = atan(1.0)*4; const double ESP = 10e-8; using namespace std; vector<int>G[MAXN]; int d[MAXN][4]; bool vis[MAXN]; int n; void dp(int u){ vis[u] = 1; int len = G[u].size(); d[u][0] = 1; //u是服务器，其子节点既可以是服务器，也可以不是，其父节点可以是服务器，也可以不是 d[u][1] = 0; //u不是服务器，但是u父亲是服务器，所以其子节点都不是服务器 d[u][2] = INF; // u，和u的父亲都不是服务器，所以u的子节点必须有点是服务器 vector<int>arr; for(int i = 0;i < len;i++){ int v = G[u][i]; if(vis[v]) continue; dp(v); arr.push_back(v); d[u][0] += min(d[v][0],d[v][1]); // 子节点既可以是服务器又可以不是服务器所以取最小值 d[u][1] += d[v][2]; // u不是服务器，子节点不是服务器，所以等于d[v][2]父亲和其本身都不是服务器的相加 } len = arr.size(); for(int i = 0;i < len;i++){ int v = arr[i]; d[u][2] = min(d[u][2],d[u][1] - d[v][2] + d[v][0]); } } int main(){ // freopen("input.txt","r",stdin); while(~scanf("%d",&n)){ for(int i = 0;i <= n;i++){ G[i].clear(); } memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); for(int i = 1;i < n;i++){ int a,b; scanf("%d%d",&a,&b); G[b].push_back(a); G[a].push_back(b); } dp(1); int ans = INF; ans = min(d[1][0],d[1][2]); printf("%d ",ans); scanf("%d",&n); if(n < 0) break; } return 0; }