poj_1464 动态规划
2024-09-01 07:45:43
题目大意
N个节点构成一棵树形结构,在其中若干个节点上放置士兵,与被放置士兵的节点相连的边会被士兵看守。问需要至少在多少个节点上放置士兵,才能使得N-1条边都被看守。
题目分析
题目描述的结构为树形,且最优化问题,可以考虑使用树形动态规划来解决。将结构按照树根在上,树叶在下的结构进行排列,为了保证无后效性,需要对i节点上有无士兵的情况单独处理,设置状态 dp[i][0] 表示在节点i不放置士兵的情况下,节点i以下的边都被看守所需要放置士兵的最少数目;dp[i][1]表示在节点i放置士兵的情况下,节点i以下的所有边都被看守所需要放置士兵的最少数目。显然有递推关系:
dp[i][0] = sum{dp[son_of_i][1]}
dp[i][1] = sum{min{dp[son_of_i][0], dp[son_of_i][1]}}
实现(c++)
#include<stdio.h>
#include<vector>
#include<string.h>
#define min(a, b) a < b? a:b
using namespace std;
vector<int> gGraph[1505];
//使用 vector<int> gGraph[1505], 而不使用 vector<vector<int> >
//是因为题目多组数据,若使用 vector<vector<int> >,则在每组数据都会进行对 外层vecotr的 resize操作,减低效率
int dp[1505][2];
void Travel(int node){
if (gGraph[node].empty()){
dp[node][0] = 0; //node节点不放置士兵的情况下,node节点以下的所有边都被看守所需要的士兵总数
dp[node][1] = 1; //node节点放置士兵的情况下,node节点以下的所有边都被看守所需要的士兵总数
return;
}
dp[node][1] = 1;
for (int i = 0; i < gGraph[node].size(); i++){
Travel(gGraph[node][i]); //由叶子到根进行递推,后序遍历 //node节点不放置士兵的情况下,需要node节点的子节点都放置士兵
dp[node][0] += dp[gGraph[node][i]][1]; //node节点放置士兵,则其子节点可放可不放,选取最小值即可
dp[node][1] += min(dp[gGraph[node][i]][1], dp[gGraph[node][i]][0]); }
} int main(){
int n, root;
while (scanf("%d", &n) != EOF){ for (int i = 0; i < n; i++){
gGraph[i].clear();
} int node, num_adjacent, node_adjacent;
root = -1;
memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++){
scanf("%d:(%d)", &node, &num_adjacent);
if (root < 0)
root = node;
for (int j = 0; j < num_adjacent; j++){
scanf("%d", &node_adjacent);
gGraph[node].push_back(node_adjacent);
}
} Travel(root); int result = min(dp[root][0], dp[root][1]);
printf("%d\n", result);
}
return 0;
}
最新文章
- Yii2 modal中 ajax提交表单
- ssh
- C# 根据正则表达式来判断输入的是不是数字
- Jenkins实现生产环境部署文件的回滚操作(Windows)
- CSS等高布局
- Ant 执行 YUICompressor
- SSH_框架整合5--验证用户名是否可用
- Java中的大数处理类BigInteger和BigDecimar浅析
- c语言与c++基础知识
- bootstrap-treeview
- 自己动手,丰衣足食!一大波各式各样的ImageView来袭!
- 关于bootstrap 在MVC里 模态框里加载iframe页面做编辑的时候
- (iOS)关于@property和@synthesize的理解(原创)
- leetcode题解-122买卖股票的最佳时期
- Failed to mount component: template or render function not defined.
- 个人作业——final
- java-代码生成器
- CA证书扫盲,https讲解
- 如何读取抓取的wifi包内容
- 20169205 2016-2017-2 实验二nmap的使用与分析
热门文章
- USES_CONVERSION的使用和注意
- 百度MIP(百度版的google AMP)了解一下?
- Genral log(普通日志)与 Slow log(慢速日式)
- 编写每天定时切割Nginx日志的脚本
- atitit.自动生成数据库结构脚本,或者更换数据库,基于hibernate4
- 【LeetCode】Permutations II 解题报告
- HotSpot模板解释器目标代码生成过程源码分析
- 【LeetCode】065-验证数字
- lo4j 日志级别
- HADOOP 2.6 INSTALLING ON UBUNTU 14.04 (hadoop 2.6 部署到ubuntu 14.04上面)