【hiho一下第十二周】刷油漆
2024-08-31 10:35:49
【题目链接】:http://hihocoder.com/problemset/problem/1055
【题意】
【题解】
设f[x][i]表示以第x个节点为根的子树;
不选x这个节点,然后子树里面选i个其他点能够获得的最大价值;
在枚举儿子y的时候进行DP,第一层枚举这个子树里面选了多少个节点i->逆序枚举,用01背包的更新方式节省空间;
第二层,枚举这个儿子的子树里面选了几个节点k(也不包括这个儿子节点);
则
f[x][i] = max(f[x][i],f[x][i-k]+f[y][k-1]+v[y])
//因为f[x][i]不包括x节点本身,然后y以下有k个节点,则对应的状态应该是f[y][k-1]+v[y];
在根节点(任选)上面再加1个0号节点;
最后直接输出f[0][m]
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 110;
int n,m,v[N],f[N][N];
vector <int> g[N];
void dfs(int x,int num,int fa)
{
for (int y:g[x])
{
if (y==fa) continue;
dfs(y,num-1,x);
rep2(i,num,0)
rep1(k,1,i)
f[x][i] = max(f[x][i],f[x][i-k]+f[y][k-1]+v[y]);
}
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use
cin >> n >> m;
rep1(i,1,n)
cin >> v[i];
rep1(i,1,n-1)
{
int x,y;
cin >> x >> y;
g[x].pb(y),g[y].pb(x);
}
g[0].pb(1);
dfs(0,m,-1);
cout << f[0][m] << endl;
return 0;
}
最新文章
- Ubuntu下配置Samba服务器
- C#学习笔记-数据的传递以及ToolStripProgressBar
- 【工具使用】sublime text3
- Codeforces Round #202 (Div. 2) A,B
- js时间格式化(yy年MM月dd日 hh:mm)
- django(五)
- C++学习笔记5:如何给变量及函数命名?
- iphone/ipad关于size, frame and bounds总结和UIScroll view学习笔记
- Oracle 导入导出数据 imp/exp impdp/expdp
- hibernate3和spring整合的一些方式
- Spark MLlib Deep Learning Convolution Neural Network (深度学习-卷积神经网络)3.1
- A Simple Actions Recognition System
- Java 的性能优化
- 疯狂html5演讲(两):HTML5简经常使用的元素和属性(一个):html5保留经常使用的元素
- Weex系列二、显示图片
- 一道面试题引发的思考(C#值类型和引用类型)
- SQL Server 查找统计信息的采样时间与采样比例
- NodeJs 设置跨域后页面全部变成了源码在浏览器上显示
- python使用requests库爬取网页的小实例:爬取京东网页
- struts2简单入门-关于Result标签Type属性的说明
热门文章
- UVA 11383 - Golden Tiger Claw(二分图完美匹配扩展)
- [LeetCode]Wildcard Matching 通配符匹配(贪心)
- 字符串函数---strcmp()与strncmp()详解及实现【转】
- xss 记录cookie
- if,elif,else的关系 input print int的用法
- Hadoop MapReduce编程 API入门系列之网页流量版本1(二十一)
- javascript中in运算符的介绍
- hdu3873 Invade the Mars 有限制的最短路
- 高德地图开发之获取SHA1码
- Domain=NSOSStatusErrorDomain Code=1937337955 关于iOS录音AVAudioRecorder与音频播放AVAudioPlayer真机调试录音不能播放的问题