NO1：
小強尋寶1題目描述：小強在１號結(jié)點。每個結(jié)點上都有一個門，小強要打開它需要一定的能量,只有打開了它，小強才能進入它的子樹，每個門中有一定量的寶物，也只有打開了門，小強才能取得這些寶物。給定有限能量Power的情況下，小強最多能拿到多少寶物。
輸出最多能拿到的寶物數(shù)。
這道題很明顯是一道樹形dp，題目意思也很清晰明了，當時比賽的時候和甘甜分析了一下dp的狀態(tài)方程，開始我們還覺得和采花挺像的，但是后來發(fā)現(xiàn)，他的狀態(tài)轉(zhuǎn)移明顯要比采花要簡單，因為采花那題往回走的話也要消耗步數(shù)的，而這里往回走的話并不需要消耗能量，其實根的最大寶物數(shù)只不過是基于給子數(shù)不同能量分配的前提條件下所能獲得最大寶物數(shù)而已，但是問題又出現(xiàn)了，這并不是一個二叉樹，如果一個根的直接兒子很多的話，能量分配的情況也是很多的，所以我們要將它轉(zhuǎn)化成二叉樹來做，只要在右兒子是兄弟的問題上要小心處理一下
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];}
}
這是我的多叉樹轉(zhuǎn)二叉的方程，嚴格遵循左兒子右兄弟
#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，錯了很久，今天本來做最后一次嘗試，不過我發(fā)現(xiàn)一個問題，就是做dp題，如果很多測試數(shù)據(jù)都能通過的情況下，但是個別有問題，則要么是題目的邊界點你沒考慮，要么就是狀態(tài)方程出了問題，這一次我就是
這道題我設(shè)了三個狀態(tài)
int s1[MaxN],s2[MaxN],s3[MaxN];
//s1-->是指在根節(jié)點設(shè)崗位最小cost
//s2-->是指在根節(jié)點不設(shè)崗位但能保護根的最小cost
//s3-->是指在根節(jié)點不設(shè)崗位但不能保護根或能保護根的的最小cost
s1[root]這個狀態(tài)的轉(zhuǎn)移是我一直出問題的地方，一開始我認為的是 所有子樹min(s2[son],s3[son])加起來
因為我認為s1[son]肯定會大于s2[son]，這就不對了，應(yīng)該是min(s1[son],min(s2[son],s3[son]))加起來
其實這樣好像還是有點多余，s2[son]應(yīng)該肯定會大于s3[son]吧？？這一點我倒還沒有驗證，但是我感覺是的
s2[root]這個狀態(tài)轉(zhuǎn)移要注意的就是如果子樹取得都是s2[son]，就是在son處都沒有設(shè)守衛(wèi)，那么root是沒有辦法監(jiān)控的，我們要找個s1[son]-s2[son]最小的地方替換他，這里我認為是找s1[son]-s2[son]最小，而不是單純的找s1[son]最小
s3[root]這個狀態(tài)轉(zhuǎn)移還是好辦的
還有一點，就是這道題的根我是用1處理的，所以在存圖的是要把兩個方向都存好，不能認為輸入的第一結(jié)點就是根，跟在他后面的就是它的子
#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 閱讀(534)
評論(2) 編輯 收藏 引用 所屬分類:
acm 、
動態(tài)規(guī)劃