NO1：
小强寻宝1题目描述：小强在１号结点。每个结点上都有一个门，小强要打开它需要一定的能量,只有打开了它，小强才能进入它的子树，每个门中有一定量的宝物，也只有打开了门，小强才能取得这些宝物。给定有限能量Power的情况下，小强最多能拿到多少宝物。
输出最多能拿到的宝物数。
这道题很明显是一道树形dp，题目意思也很清晰明了，当时比赛的时候和甘甜分析了一下dp的状态方程，开始我们还觉得和采花挺像的，但是后来发现，他的状态转移明显要比采花要简单，因为采花那题往回走的话也要消耗步数的，而这里往回走的话并不需要消耗能量，其实根的最大宝物数只不过是基于给子数不同能量分配的前提条件下所能获得最大宝物数而已，但是问题又出现了，这并不是一个二叉树，如果一个根的直接儿子很多的话，能量分配的情况也是很多的，所以我们要将它转化成二叉树来做，只要在右儿子是兄弟的问题上要小心处理一下
void build_tree(
int now)
{
int i,next;
flag[now]=1;
for(i=1;i<=adj[now][0];i++)
if(!flag[adj[now][i]]){
next=Lson[now]=adj[now][i];
build_tree(adj[now][i]);
break;}
for(i++;i<=adj[now][0];i++)
if(!flag[adj[now][i]]){
Rson[next]=adj[now][i];
build_tree(adj[now][i]);
next=Rson[next];}
}
这是我的多叉树转二叉的方程，严格遵循左儿子右兄弟
#include<iostream>
#define MaxN 105
#define max(a,b) (a>b?a:b)
int Lson[MaxN],Rson[MaxN];
int cost[MaxN],key[MaxN];
int adj[MaxN][MaxN];
int N,Power,flag[MaxN];
int num[MaxN][MaxN];
void build_tree(int now)
{
int i,next;
flag[now]=1;
for(i=1;i<=adj[now][0];i++)
if(!flag[adj[now][i]]){
next=Lson[now]=adj[now][i];
build_tree(adj[now][i]);
break;}
for(i++;i<=adj[now][0];i++)
if(!flag[adj[now][i]]){
Rson[next]=adj[now][i];
build_tree(adj[now][i]);
next=Rson[next];}
}
int dp(int now,int p)
{
int i;
if(num[now][p])return num[now][p];
if(!Rson[now]&&!Lson[now])return num[now][p]=p>=cost[now]?key[now]:0;
if(!Lson[now]){
num[now][p]=dp(Rson[now],p);
if(p>=cost[now])num[now][p]=max(num[now][p],key[now]+dp(Rson[now],p-cost[now]));
return num[now][p];
}
if(!Rson[now]){
if(p>=cost[now])
return num[now][p]=dp(Lson[now],p-cost[now])+key[now];
else return num[now][p]=0;}
num[now][p]=dp(Rson[now],p);
for(i=cost[now];i<=p;i++)
num[now][p]=max(num[now][p],key[now]+dp(Lson[now],i-cost[now])+dp(Rson[now],p-i));
return num[now][p];
}
int main()
{
int i,u,v;
while(scanf("%d%d",&N,&Power)!=EOF){
memset(Lson,0,sizeof(Lson));
memset(Rson,0,sizeof(Rson));
memset(cost,0,sizeof(cost));
memset(key,0,sizeof(key));
memset(adj,0,sizeof(adj));
memset(num,0,sizeof(num));
memset(flag,0,sizeof(flag));
for(i=1;i<=N;i++)
scanf("%d%d",&cost[i],&key[i]);
for(i=1;i<N;i++){
scanf("%d%d",&u,&v);
adj[u][++adj[u][0]]=v;
adj[v][++adj[v][0]]=u;}
build_tree(1);
printf("%d\n",dp(1,Power));
}
return 0;
}
下面一道树形dp
Guard，错了很久，今天本来做最后一次尝试，不过我发现一个问题，就是做dp题，如果很多测试数据都能通过的情况下，但是个别有问题，则要么是题目的边界点你没考虑，要么就是状态方程出了问题，这一次我就是
这道题我设了三个状态
int s1[MaxN],s2[MaxN],s3[MaxN];
//s1-->是指在根节点设岗位最小cost
//s2-->是指在根节点不设岗位但能保护根的最小cost
//s3-->是指在根节点不设岗位但不能保护根或能保护根的的最小cost
s1[root]这个状态的转移是我一直出问题的地方，一开始我认为的是 所有子树min(s2[son],s3[son])加起来
因为我认为s1[son]肯定会大于s2[son]，这就不对了，应该是min(s1[son],min(s2[son],s3[son]))加起来
其实这样好像还是有点多余，s2[son]应该肯定会大于s3[son]吧？？这一点我倒还没有验证，但是我感觉是的
s2[root]这个状态转移要注意的就是如果子树取得都是s2[son]，就是在son处都没有设守卫，那么root是没有办法监控的，我们要找个s1[son]-s2[son]最小的地方替换他，这里我认为是找s1[son]-s2[son]最小，而不是单纯的找s1[son]最小
s3[root]这个状态转移还是好办的
还有一点，就是这道题的根我是用1处理的，所以在存图的是要把两个方向都存好，不能认为输入的第一结点就是根，跟在他后面的就是它的子
#include<iostream>
#define MaxN 1505
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define inf 1<<30
using namespace std;
int cost[MaxN],n;
int s1[MaxN],s2[MaxN],s3[MaxN];
int adj[MaxN][MaxN];
void dp(int now,int did)
{
int i,tmp=inf,k,flag=0,klag=0;
int b1=0,b2=0,b3=0;
if(s1[now]!=-1)return;
for(i=1;i<=adj[now][0];i++)
if(adj[now][i]!=did){
flag=1;
dp(adj[now][i],now);
if((s1[adj[now][i]]-s2[adj[now][i]])>0&&tmp>s1[adj[now][i]]-s2[adj[now][i]]){
tmp=s1[adj[now][i]]-s2[adj[now][i]];
k=i;
}}
for(i=1;i<=adj[now][0];i++)
if(adj[now][i]!=did){
b1+=min(s1[adj[now][i]],min(s2[adj[now][i]],s3[adj[now][i]]));
b3+=min(s1[adj[now][i]],s2[adj[now][i]]);
if(s1[adj[now][i]]>s2[adj[now][i]])b2+=s2[adj[now][i]];
else {klag=1;b2+=s1[adj[now][i]];}
}
if(!flag){s1[now]=cost[now]; s2[now]=inf ;s3[now]=0; return;}
s1[now]=b1+cost[now];
if(!klag)s2[now]=b2+s1[adj[now][k]]-s2[adj[now][k]];
else s2[now]=b2;
s3[now]=b3;
}
int main()
{
int t,cos,m,p;
memset(s1,-1,sizeof(s1));
memset(s2,-1,sizeof(s2));
memset(s3,-1,sizeof(s3));
scanf("%d",&n);
while(n--){
scanf("%d%d%d",&t,&cos,&m);
cost[t]=cos;
while(m--){
scanf("%d",&p);
adj[t][++adj[t][0]]=p;
adj[p][++adj[p][0]]=t;
}
}
dp(1,0);
printf("%d\n",min(s1[1],s2[1]));
return 0;
}
posted on 2008-05-03 15:45
zoyi 阅读(509)
评论(2) 编辑 收藏 引用 所属分类:
acm 、
动态规划