T^T 粗心害死人。。

明明可以直接过的,但是有一个数组元素下标会为-1.。。
不过为什么不是RE 而是WA了=.=..

1 条评论

  • @ 2017-02-18 15:03:39
    // input code here
    ```//都不忍心说水了QAQOwO
    #include<bits/stdc++.h>
    using namespace std;
    struct node{
        int son[1001];
        int sonnum;
        int price;
        int fa;
    }a[1501];
    int treedp[1501][2][2];
    int n;
    void init()
    {
        cin>>n;
        int num;
        for(int i=1;i<=n;i++)
        {
            cin>>num;
            cin>>a[num].price;
            cin>>a[num].sonnum;
            for(int j=1;j<=a[num].sonnum;j++)
            {
                cin>>a[num].son[j];
                a[a[num].son[j]].fa=num;
            }
            
        }
    }
    int getfa(int x)
    {
        if (a[x].fa==0) return x;
        else return (getfa(a[x].fa));
    }
    int getmin(int x,int y,int z)
    {
        int asjklf=min(x,y);
        asjklf=min(asjklf,z);
        return asjklf; 
    }
    int dp(int x,int self,int sonif)
    {
        if(a[x].sonnum==0&&self) return a[x].price;
        if(a[x].sonnum==0) return 1234511;
        if (treedp[x][self][sonif]) return treedp[x][self][sonif];
        if(self&&sonif)
        {
            treedp[x][self][sonif]=a[x].price;
            for(int i=1;i<=a[x].sonnum;i++)
            {
                int j=a[x].son[i];
                treedp[x][1][1]+=getmin(dp(j,1,1),dp(j,0,1),dp(j,0,0));
            }
        }
        if(!self&&!sonif)
        {
            for(int i=1;i<=a[x].sonnum;i++)
            {
                int j=a[x].son[i];
                treedp[x][0][0]+=dp(j,0,1);
            }
        }
        if(!self&&sonif)
        {
            int ll=a[x].son[1];
            bool al=0;
            int bit=dp(ll,1,1)-dp(ll,0,1);
            for(int i=1;i<=a[x].sonnum;i++)
            {
                int j=a[x].son[i];
                int ppg=dp(j,1,1)-dp(j,0,1);
                if(ppg<=0)
                {
                    treedp[x][0][1]+=ppg;
                    al=1;
                }
                bit=min(bit,dp(j,1,1)-dp(j,0,1));
                treedp[x][0][1]+=dp(j,0,1);
            }
            if(!al)
            treedp[x][0][1]+=bit;
        }
        return treedp[x][self][sonif]; 
    }
    int main()
    {
        init();
        int gen=getfa(1);
        int ans=min(dp(gen,0,1),dp(gen,1,1));
        cout<<ans;
    } 
    
  • 1

信息

ID
1144
难度
7
分类
动态规划 | 树形DP 点击显示
标签
递交数
4561
已通过
1001
通过率
22%
被复制
10
上传者