首页 > 代码库 > POJ3345
POJ3345
http://poj.org/problem?id=3345
大意：
大意是说现在有n个城市来给你投票，你需要至少拿到m个城市的赞成票。想要获得第i个城市的赞成需要花费w[i]，有个条件就是某些城市是在其他某个城市的统治下的，当获得某个城市的赞成票后，那么他所统治的其他城市都会投票给你（不再需要花费），球最小花费
题解：
我们很容易看出这个统治关系组成了一个树的结构，就等于拿到i整个子树的所有节点的花费就是节点i的花费，求最后拿到>=m个节点的最小花费
我的状态也是按照题目要求设的，F[i]表示到目前为止得到i个城市的赞成的最小花费，然后进行树上DP。
F[i] = min{F[i-num[u]] + w[u]}
其中u表示当前所处的节点，num[u]表示节点u子树上节点数量
这里这样DP是会有问题的，就是我们不能在子节点的F值算出来后再算父节点的F值，否则就可能存在用子节点选择了的状态更新父节点选择的状态，也就是说在DFS时，只能先算父节点的F值，再进行dfs算子节点的
另外这里的F[i-num[u]]实际上只能是由节点u的已经算出的兄弟节点推到（就是说在考虑节点u加入时，他的父节点是不能被加入了的）
上面两个要求统一起来就是说计算父节点的F值（吧父节点加入），子节点的不可以先被计算出；计算子节点的F值时，父节点不可以先加入。解决办法就是另外开一个数组G[i][j]，用来临时存放节点i往下递归前的结果，回溯时再更新
上面的F，G对应下面的DP,DP2
dfs1用来计算num数组，dfs2是DP过程，复杂度O(n^2)
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype> 10 #include <cstring> 11 #include <cstdlib> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 #define INF 1e9 16 #define inf (-((LL)1<<40)) 17 #define lson k<<1, L, mid 18 #define rson k<<1|1, mid+1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FOPENIN(IN) freopen(IN, "r", stdin) 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 24 #define rep(i, a, b) for(int i = a; i <= b; i ++) 25 template<class T> T CMP_MIN(T a, T b) { return a < b; } 26 template<class T> T CMP_MAX(T a, T b) { return a > b; } 27 template<class T> T MAX(T a, T b) { return a > b ? a : b; } 28 template<class T> T MIN(T a, T b) { return a < b ? a : b; } 29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; } 31 32 typedef __int64 LL; 33 //typedef long long LL; 34 const int MAXN = 1005; 35 const int MAXM = 1000006; 36 const double eps = 1e-10; 37 const LL MOD = 1000000007; 38 39 bool G[210][210]; 40 map<string, int>M; 41 int cnt, w[210], dp[210], dp2[210][210], n, m; 42 char str[110], s[40000]; 43 int num[210], tot; 44 45 int get_index(char* s) 46 { 47 if(M[s]) return M[s]; 48 return M[s] = ++cnt; 49 } 50 51 void init() 52 { 53 int x, no; 54 cnt = 0; M.clear();tot = 0; 55 mem0(G); mem0(dp); mem0(num); 56 sscanf(s, "%d %d", &n, &m); 57 for(int i = 1; i <= n; i ++) G[0][i] = 1; 58 for(int i = 1; i <= n; i ++) 59 { 60 gets(s); 61 sscanf(s,"%s %d%*c", str, &x); 62 if( !M[str] ) M[str] = ++cnt; 63 w[no = M[str]] = x; 64 int len = strlen(s), p = len - 1, index = 0; 65 while( !isdigit(s[p]) ) p --; p ++; 66 if(p == len) continue; 67 p++; 68 while(p <= len) 69 { 70 if(p == len || s[p] == ‘ ‘) 71 { 72 str[index] = 0; 73 int id = get_index(str); 74 G[no][id] = 1; 75 G[0][id] = 0; 76 index = 0; 77 } 78 else str[index++] = s[p]; 79 ++p; 80 } 81 } 82 } 83 84 void dfs1(int u) 85 { 86 dp[u] = INF; 87 num[u] = 1; 88 for( int i = 1; i <= n; i ++) if( G[u][i] ) 89 { 90 dfs1(i); 91 num[u] += num[i]; 92 } 93 dp[0] = 0; 94 } 95 96 void dfs2(int u) 97 { 98 memcpy(dp2[u], dp, sizeof(dp)); 99 if(u) for(int i = tot; i >= 0; i --)100 {101 dp2[u][i + num[u]] = min(dp[i + num[u]], dp[i] + w[u]);102 }103 for(int i = 1; i <= n; i ++) if(G[u][i])104 dfs2(i);105 for(int i = 0; i <= n; i ++)106 dp[i] = min(dp[i], dp2[u][i]);107 tot ++;108 }109 110 void print()111 {112 int ans = INF;113 for(int i = m; i <= n; i ++)114 ans = min(ans, dp[i]);115 printf("%d\n", ans);116 }117 118 int main()119 {120 // freopen("in.txt", "r", stdin);121 // freopen("out.txt", "w", stdout);122 while(gets(s) && s[0] != ‘#‘)123 {124 init();125 dfs1(0);126 dfs2(0);127 print();128 }129 return 0;130 }
POJ3345
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。