题目
题意
- 每一个人都有一个快乐程度\(R_i\)
- 若一个人参见了晚会，那么他的上司不能参加晚会
- 求最大的快乐程度
题解
- 确认状态：dp[u][state]:若state == 0, 表示不选择\(node_u\)所得到的最大的快乐指数； 若state == 1, 表示选择\(node_u\)得到的最大的快乐指数。
- 状态转移方程：
dp[u][0] = \(\sum_{allson} min(dp[v][0], dp[v][1])\);
dp[u][1] = \(\sum dp[v][0]\)
最后要dp[u][1] += \(R_i\) - 边界条件：dp[u][0] = 0, dp[u][1] = \(R_i\);i为叶子节点
- 结果:max(dp[root][0], dp[root][1])
代码
|
|
题目
题意
- 有N个节点，N-1条边，边有权重
- 保留M条边，使权重和最大
题解
- 确认状态：dp[u][j]:表示在以u为根的子树保留j个分支可以得到的最大苹果数量
- 状态转移方程：
dp[u][j] = max(dp[u][k] + dp[v][j-k-1]+weight)
v分别是u的儿子，weight为u到v边上的苹果数目, k属于[0, j] - 边界条件：
- 结果：dp[1][M]
代码
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950using namespace std;const int maxn = 105;struct Node{int to;int next;int weight;}edge[maxn];int head[maxn];int n, q;int dp[maxn][maxn];int tot=0;void add_edge(int u, int v, int weight){edge[tot].to = v;edge[tot].weight = weight;edge[tot].next = head[u];head[u] = tot++;}bool vis[maxn];void dfs(int u){vis[u] = true;for(int i=head[u]; i!=-1; i = edge[i].next){int v = edge[i].to;int weight = edge[i].weight;if(vis[v]) continue;dfs(v);for(int k=q; k>=1; k--){for(int j=1; j<=k; j++){//想想可以保留的边数超过了总边数会怎么样？dp[u][k] = max(dp[u][k], dp[u][k-j]+dp[v][j-1]+weight);}}}}int main(){while(~scanf("%d%d", &n, &q)){tot = 0;memset(vis, 0, sizeof(vis));memset(head, -1, sizeof(head));memset(dp, 0, sizeof(dp));for(int i=1; i<=n-1; i++){int u, v, weight;scanf("%d%d%d", &u, &v, &weight);add_edge(u, v, weight);}dfs(1);printf("%d\n", dp[1][q]);}return 0;}
题目
题意
- 一个节点上放一个士兵，一个士兵可以看守所有的相邻的边。
- 求最小的士兵数目，使每一条边都被覆盖
题解
- 确认状态：dp[u][state]:state == 0时，以x为根的子树在x上放置的士兵的最少所需的士兵数目；state == 1时，不以x为根的子树在x上放置的士兵的最少所需的士兵数目
状态转移方程：
dp[u][1] = 1+ \(\sum min(dp[v][0], dp[v][1])\)
dp[u][0] = \(\sum dp[v][1]\)边界条件：
- 结果：min(f[root][0], f[root][1])
代码
|
|
题目
题意
- 树的最小点覆盖。一个点可以覆盖相邻的点
- 求最小的点数。（即最小点覆盖问题）最小点覆盖在一般图中是NP难题，因此在特定的数据结构中才会有高效的算法
注意和上面的题目的区别！！！~~~~
题解
*确认状态： ①dp[u][0]：选点u，并且以点u为根的子树都被覆盖了。
②dp[u][1]：不选点u, u被其儿子覆盖
③dp[u][2]：不选点u，u没有被子节点覆盖（被其父亲覆盖）状态转移方程：
dp[u][0]=1+\(\sum min(dp[v][0],dp[v][1],dp[v][2])\) （v是u的儿子）
dp[u][2]=\(\sum min(dp[v][1], dp[v][0])\)
dp[u][1]的情况复杂一些：
if(i没有子节点)dp[i][1]=INF
想想什么时候初值的时候设置成INF，什么时候设置成0。
else dp[u][1]=\(\sum min(dp[v][0],dp[v][1])\)+inc
其中对于inc有：
if(上面式子中的\(\sum min(dp[v][0],dp[v][1])\)中包含某个dp[v][0]) inc=0;
else inc=min(dp[v][0]-dp[v][1])
ps:这里的inc相当于强行让一个子节点上放了一个节点使其能够覆盖到父亲节点。选择的依据就是dp[u][0]-dp[u][1]的最小值。边界：
dp[u][0] = 1;
dp[u][1] = dp[u][2] = 0;结果：min(dp[1][0], dp[1][1])
代码
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364using namespace std;const int maxn = 1e4+10;const int INF = 1e9;int dp[maxn][3];bool vis[maxn];struct Node{int to;int next;int weight;}edge[maxn*2];//数组一开始没有开二倍，emmmmmmmmmmmmmmmmmint n;int head[maxn];int tot;void add_edge(int u, int v){edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;}void dfs(int u){vis[u] = true;dp[u][0] = 1;dp[u][1] = dp[u][2] = 0;bool flag = true;int temp = INF;for(int i = head[u]; i!= -1; i = edge[i].next){int v = edge[i].to;if(vis[v]) continue;dfs(v);dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));dp[u][2] += min(dp[v][1], dp[v][0]);//由父亲决定if(dp[v][0]<=dp[v][1]){flag = false;dp[u][1] += dp[v][0];}else {dp[u][1] += dp[v][1];temp = min(temp, dp[v][0]-dp[v][1]);}}if(flag){dp[u][1] += temp;}}int main(){while(~scanf("%d", &n)){tot = 0;memset(head, -1, sizeof(head));memset(dp, 0, sizeof(dp));memset(vis, 0, sizeof(vis));for(int i=1; i<=n-1; i++){int u, v;scanf("%d%d", &u, &v);add_edge(u, v);add_edge(v, u);}dfs(1);printf("%d\n", min(dp[1][0], dp[1][1]));}return 0;}
source
雨姐姐的PP踢