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 閱讀(528)
評論(2) 編輯 收藏 引用 所屬分類:
acm 、
動態規劃