http://acm.hdu.edu.cn/showproblem.php?pid=4340
樹型dp 理解起來并不難但是狀態(tài)有點多 比賽的時候沒敢寫
解題上好像是用的三維數(shù)組 有兩個維大小是2 的?
自己干脆寫了6個一維數(shù)組 ?然后6個dp函數(shù)相互調(diào)用 ?雖然代碼有點長
但是理解方便 思路也比較清晰
對予一個子樹的根節(jié)點 有6中方法
1 ?A從這里進(jìn)攻
2 ?B從這里進(jìn)攻
3 ?A攻擊這里時間花一半 因為上面的相鄰城市A 已經(jīng)提前攻破
4 ?B-------------------------------------
5 ?A攻擊這里花一半時間 ?因為下面的某個相鄰城市已經(jīng)被A提前攻破
6 ?B-----------------------------------
對于沒種狀態(tài) ?向下選取攻擊方法的時候 選擇合適的 ?最恰當(dāng)?shù)?
代碼及其注釋:
#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已經(jīng)提前攻破 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ài)向下傳遞兩個情況) } 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 這個節(jié)點進(jìn)行dp 只有這4 種狀態(tài) 選最小的那個 ans=MIN(ans,dpa1(1,0),dpb1(1,0)); printf("%d\n",ans); Dele(n); } return 0; }
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
