- 小胖守皇宫
- 2014-09-07 17:18:48 @
明明可以直接过的,但是有一个数组元素下标会为-1.。。
不过为什么不是RE 而是WA了=.=..
1 条评论
-
810600709@qq.com LV 7 @ 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