http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3506
题目大意为给定一颗节点带权值的树,和整数k,要求给出一个策略,对这棵树切k刀(对边切,切完保留一部分,丢弃一部分),最后得到的部分的权值和为最大/最小。
f[i][j]为以第i个节点为根,切k刀所得到的最小值。普通dp的想法就是对于某一个节点,如果它为根并保留到最后,那么就在所有的边N中选取k条边,共有C(N,k)种情况,遍历每种情况更新f[i][k].显然这种方法效率是指数级的,会TLE。
那么如果以节点i为根递归的遍历i的子节点,来更新f[i][0],f[i][1]...f[i][k],就可以在1个DFS的时间内完成整个DP过程。因此有一下思路,对于节点i的子节点j,考虑3中情况
1)子节点j对应的子树保留,但是子树切1---m刀,节点i对应的树切m-1---0刀。3)子节点j对应的树不保留(也就是说子节点j对应的树至少切1刀)
情况1:f[i][j]=min(f[i][j],f[i][j-m]+f[j][k-m])
情况2:f[i][j]=min(f[i][j],f[i][k-m])(m=1----k)
注意1:在更新子节点j之前应该先将f[i][m]初始化f[i][m]+=f[j][0];
注意2:在更新f[i][0]----f[i][k]的过程中一定要逆序更新,因为在更新f[i][j]的时候所用到的子结构f[i][0]---f[i][j-1]应该是上一个子节点更新之后的。如
注意3:最后的结果也是递归的查找,如果根节点1不再最后的结果中,那么递归的遍历他的子节点,对于子节点j,遍历f[j][p],其中p的取值应该是max(0,k-除j子树之外的所有边树)---j子树中的所有边数
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string.h>
using namespace std;
const int maxn=1005;
const int inf=99999999;
int fir[maxn],next2[maxn*2],to[maxn*2];
int num[maxn];
int n,m;
int f[maxn][22];
int value[maxn];
int edgenum;
vector<int>v[maxn];
void add_edge(int u,int v)
{
next2[edgenum]=fir[u];
fir[u]=edgenum;
to[edgenum]=v;
edgenum++;
}
void dfs(int u,int fa)
{
int size=v[u].size();
for(int i=0;i<size;i++)if(v[u][i]!=fa)
{
add_edge(u,v[u][i]);
dfs(v[u][i],u);
}
}
void solve(int u,int p)
{
num[u]=1;
f[u][0]=value[u];
for(int j=1;j<=m;j++)f[u][j]=inf;
f[u][0]=0;
for(int e=fir[u];e!=-1;e=next2[e])
if(to[e]!=p)
{
int v=to[e];
solve(v,u);
num[u]+=num[v];
for(int j=m;j>=0;j--)
{
f[u][j]+=f[v][0]; //!!注意1
for(int k=0;k<j;k++)//k!=j 注意2
{
f[u][j]=min(f[u][j],f[u][k]+f[v][j-k]);
}
for(int k=1;k<=j&&k<=num[v];k++)
{
f[u][j]=min(f[u][j],f[u][j-k]);
}
}
}
for(int j=0;j<=m;j++)f[u][j]+=value[u];
}
int DP()
{
int ans=inf;
solve(1,-1);
ans=min(ans,f[1][m]);
if(m>0){
for(int i=2;i<=n;i++)
for(int j=max(m+num[i]-num[1],0);j<num[i]&&j<m;j++)//!注意3
ans=min(ans,f[i][j]);
}
return ans;
}
int main()
{
freopen("e:\\zoj\\zoj_3506.txt","r",stdin);
while(scanf("%d%d",&n,&m)==2)
{
for(int i=1;i<=n;i++)scanf("%d",&value[i]);
memset(fir,-1,sizeof(fir));
for(int i=1;i<=n;i++)v[i].clear();
edgenum=0;
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1,-1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)f[i][j]=inf;
memset(num,0,sizeof(num));
printf("%d ",DP());
for(int i=1;i<=n;i++)value[i]=-value[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)f[i][j]=inf;
memset(num,0,sizeof(num));
printf("%d\n",-DP());
}
}
分享到:
相关推荐
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
最近在acm.zju.edu.cn上通过的题目的代码,都是比较有价值的题目
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
zoj吐血制作,希望大家喜欢
zoj在线评测系统前台和后台源代码,包括比赛用的客户端源代码
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
zoj4041正确题解源代码,以及运行程序
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
浙江大学ZOJ源码题解,按照题目类型和难易分类。
acm中zoj1002的可运行C++程序
一个非常非常非常非常实用的zoj结题代码
问题:枫教授在一所大学教数学,他发现了一个函数,用于获得一个表达式的操作数的目的,函数命名op(i,e)可以描述如下:
能AC 通过的c++代码,包括zoj1002,1091,1789
zoj的代码实现,很好,而且很全面,全部实现。
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
ZOJ上的一些水题,4.16浙江省程序设计竞赛的题目
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 2536 这个不是用贪心做的
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法