http://acm.hdu.edu.cn/showproblem.php?pid=4340
樹型dp 理解起來并不難但是狀態有點多 比賽的時候沒敢寫
解題上好像是用的三維數組 有兩個維大小是2 的?
自己干脆寫了6個一維數組 ?然后6個dp函數相互調用 ?雖然代碼有點長
但是理解方便 思路也比較清晰
對予一個子樹的根節點 有6中方法
1 ?A從這里進攻
2 ?B從這里進攻
3 ?A攻擊這里時間花一半 因為上面的相鄰城市A 已經提前攻破
4 ?B-------------------------------------
5 ?A攻擊這里花一半時間 ?因為下面的某個相鄰城市已經被A提前攻破
6 ?B-----------------------------------
對于沒種狀態 ?向下選取攻擊方法的時候 選擇合適的 ?最恰當的
代碼及其注釋：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#define LL long long
using namespace std;
const int N=105;
const int M=0x3f3f3f3f;
struct node
{
struct tt *next;
}mem[N];
struct tt
{
int j;
struct tt *next;
};
int ansa[N];//A 直接攻擊這里 花費全部時間
int ansb[N];//B 直接攻擊這里 花費全部時間
int ansa0[N];// A 攻擊 一半時間 上面提前相鄰的已被 A 攻破
int ansb0[N];// B 攻擊 一半時間 上面提前相鄰的已被 B 攻破
int ansa1[N];// A 攻擊 一半時間 下面提前相鄰的已被 A 攻破
int ansb1[N];// B 攻擊 一半時間 下面提前相鄰的已被 B 攻破
int a[N],b[N];
void build(int i,int j)
{
struct tt *t=new tt;
t->j=j;
t->next=mem[i].next;
mem[i].next=t;
}
void Dele(int n)
{
for(int i=1;i<=n;++i)
mem[i].next=NULL;
}
int MIN(int x,int y,int z)
{
if(x>y)
x=y;
if(x>z)
x=z;
return x;
}
int dpb(int ,int);
int dpa0(int ,int);
int dpb0(int ,int);
int dpa1(int ,int);
int dpb1(int ,int);
int dpa(int x,int pre)
{
if(ansa[x]!=-1)
return ansa[x];
ansa[x]=a[x];// A花費全部時間攻擊這里
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(t->j!=pre)
{
ansa[x]+=MIN(dpa0(t->j,x),dpb(t->j,x),dpb1(t->j,x));//再攻擊下面的點 A 在攻擊就可以花費一半時間 B的話就不行了
}
t=t->next;
}
return ansa[x];
}
int dpb(int x,int pre)
{
if(ansb[x]!=-1)
return ansb[x];
struct tt *t=mem[x].next;
ansb[x]=b[x];
while(t!=NULL)
{
if(t->j!=pre)
{
ansb[x]+=MIN(dpb0(t->j,x),dpa(t->j,x),dpa1(t->j,x));
}
t=t->next;
}
return ansb[x];
}
int dpa0(int x,int pre)
{
if(ansa0[x]!=-1)
return ansa0[x];
ansa0[x]=a[x]/2;// A 花費一半時間 攻擊這里 上面相鄰城市 A已經提前攻破
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(t->j!=pre)
{
ansa0[x]+=MIN(dpa0(t->j,x),dpb(t->j,x),dpb1(t->j,x));//下面 A 攻擊花一半時間 B的話有兩種
}
t=t->next;
}
return ansa0[x];
}
int dpb0(int x,int pre)
{
if(ansb0[x]!=-1)
return ansb0[x];
ansb0[x]=b[x]/2;
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(t->j!=pre)
{
ansb0[x]+=MIN(dpb0(t->j,x),dpa(t->j,x),dpa1(t->j,x));
}
t=t->next;
}
return ansb0[x];
}
int dpa1(int x,int pre)
{
if(ansa1[x]!=-1)
return ansa1[x];
int temp=a[x]/2;//A花費一半時間 下面某個相鄰的城市已被提前攻破 先保存下面城市不用提前攻破的情況
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(t->j!=pre)
{
temp+=MIN(dpa0(t->j,x),dpb(t->j,x),dpb1(t->j,x));
}
t=t->next;
}
ansa1[x]=M;
t=mem[x].next;
while(t!=NULL)
{
if(t->j!=pre)
{
int k=MIN(dpa0(t->j,x),dpb(t->j,x),dpb1(t->j,x));
ansa1[x]=MIN(ansa1[x],temp-k+dpa(t->j,x),temp-k+dpa1(t->j,x));//枚舉下面哪個城市 是提前攻破的（提前攻破 有直接全部時間攻破 和 再把這樣狀態向下傳遞兩個情況）
}
t=t->next;
}
return ansa1[x];
}
int dpb1(int x,int pre)
{
if(ansb1[x]!=-1)
return ansb1[x];
int temp=b[x]/2;
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(t->j!=pre)
{
temp+=MIN(dpb0(t->j,x),dpa(t->j,x),dpa1(t->j,x));
}
t=t->next;
}
ansb1[x]=M;
t=mem[x].next;
while(t!=NULL)
{
if(t->j!=pre)
{
int k=MIN(dpb0(t->j,x),dpa(t->j,x),dpa1(t->j,x));
ansb1[x]=MIN(ansb1[x],temp-k+dpb(t->j,x),temp-k+dpb1(t->j,x));
}
t=t->next;
}
return ansb1[x];
}
int main()
{
//freopen("data.txt","r",stdin);
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
scanf("%d",&b[i]);
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d %d",&x,&y);
build(x,y);
build(y,x);
}
memset(ansa,-1,sizeof(ansa));
memset(ansb,-1,sizeof(ansb));
memset(ansa0,-1,sizeof(ansa0));
memset(ansb0,-1,sizeof(ansb0));
memset(ansa1,-1,sizeof(ansa1));
memset(ansb1,-1,sizeof(ansb1));
int ans=M;
ans=MIN(ans,dpa(1,0),dpb(1,0));//從1 這個節點進行dp 只有這4 種狀態 選最小的那個
ans=MIN(ans,dpa1(1,0),dpb1(1,0));
printf("%d\n",ans);
Dele(n);
}
return 0;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
