亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

hdu 4340 Capturing a country

系統(tǒng) 1737 0

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;

}


    

hdu 4340 Capturing a country


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 成人亚洲视频 | 伊人网伊人网 | 久久久久久97 | 91成人免费观看网站 | 免费人成激情视频在线观看冫 | 久久精品一区二区三区不卡牛牛 | 亚洲视频观看 | 免费国产不卡午夜福在线 | 久久国产精品吴梦梦 | 日韩 欧美 亚洲 国产 | 日韩精品亚洲人成在线观看 | 91久久精品都在这里 | 色94色欧美一区 | 国内精品久久久久久久97牛牛 | 免费国产视频在线观看 | 香蕉国产精品 | 波多野给衣一区二区三区 | 成人久久18免费网站 | 四虎www成人影院 | 国产v欧美v日本v精品 | 亚洲国产成人私人影院 | 四虎在线成人免费网站 | 欧美性另类69xxxx极品 | 国产一级毛片视频 | 日本亚洲精品久久 | 亚欧有色亚欧乱色视频 | 99热久 | 九九热精品 | 日本一级毛片片在线播放 | 国产视频第二页 | 亚洲欧美综合一区 | 国产精品夜色7777青苹果 | 天天操天天插天天射 | 亚洲综合欧美在线 | 日本不卡在线视频高清免费 | 久久www香蕉免费人成 | 免费观看一级特黄欧美大片 | 国产高清一区二区三区四区 | 一级毛片老太婆交性欧美 | 伊人久久久久久久久香港 | 日本aaaaa级毛片 |