M - The more, The Better （树形DP）
发布时间
阅读量：
阅读量
在战略游戏中扮演角色的ACboy常常非常着迷于探索各种可能性。地图上分布着N座相互关联的城市（或称为"目标"），每一座城市都蕴藏着独特的资源 treasure. 每次游戏时ACboy可以选择攻占M座城市来获取其中的资源 treasure. 但是由于地理分布的原因，并非所有的城市都能够直接被占领：其中一些城市无法直接攻下它们；而要攻下这些特定的防御性较高的城市，则必须首先征服它们所依赖的一个特定的基础性目标. 能否帮助ACboy找到最优策略来选择哪M个目标以最大化宝物收益？
Input
每个测试实例包含两个整数N和M（满足条件1 ≤ M ≤ N ≤ 200）。随后的N行中每一行都包含两个整数a和b。在该i行中，在 ith行列出的信息是：a表示欲攻占城堡i必须先攻下城堡a；若a=0，则表示可以直接攻占城堡i。b表示城堡i中的宝物数量（≥0）。当N = 0,M = 0时输入结束。
Output
对于每个测试实例来说，请生成一个整数值表示ACboy征服M座城堡所得的最大宝物数量
Sample Input
Sample Output
这个树有多个根节点，将这些与0节点连接，0，作为其他所有树的根节点。
dp[4][4]=max(dp[2][取k个点],dp[某个子节点][4-k]);
4
实际上并不复杂，在处理第④号节点时需要首先选择其中数量为k的点作为代表集；随后，在这些代表集中进一步在这些子节点中选择数量为（4−k）的点作为次级代表集；需要注意的是，在这一过程中始终假设所有选取操作均基于当前最优策略展开；当所有可能的（4）子节点都处理完毕后，则动态规划表中的d_p【④
#include<stdio.h>
#include<queue>
#include<stack>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=1000;
int head[1000];
int tot,n,m;
int dp[N][N];
struct node
{
int u,v,w,next;
} g[N];
void add(int u,int v,int w)
{
g[tot].v=v;
g[tot].w=w;
g[tot].next=head[u];
head[u]=tot++;
}
void init()
{
tot=0;
memset(head,-1,sizeof(head));
memset(dp,0,sizeof(dp));
memset(g,0,sizeof(g));
}
void dfs(int u)
{
for(int i=head[u];~i;i=g[i].next)
{
int v=g[i].v,w=g[i].w;
dfs(v);
for(int j=m;j>0;j--)
{
for(int k=0;k<=j-1;k++)
{
dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k-1]+w);
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0)
return 0;
init();
for(int i=1; i<=n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,i,b);
}
dfs(0);
printf("%d\n",dp[0][m]);
}
return 0;
}解题思路来自：<>
全部评论 (0)
还没有任何评论哟~