一道比较典型的树形\(DP\)吧。
- 思路: 设\(f[i][0/1][0/1]\)表示第\(i\)个点有没有安排保安(第二维),能不能被观察到(第三维),其实开两维就可以。 对于一个点\(u\),枚举它所有的儿子\(v\)(注意是求和)。\(f[u][1][1]\)对儿子的所有情况(三种\(f[v][0][0]\,,[1][1]\,,[0][1]\))取\(min\)。\(f[u][0][0]\)对\(f[v][0][1]\,,[1][1]\)两种情况取\(min\)。\(f[u][0][1]\)稍微复杂一点,于是对\(f[v][0][1]\,,[1][1]\)两种情况取\(min\),但是有可能所有的儿子都取的是\(f[v][0][1]\),这样就不合法了,必须至少有一个儿子取到\(f[v][1][1]\),才满足\(u\)点布设保安,但是被观察到(到目前为止)。所以枚举每个儿子的时候,记录一个\(f[v][1][1]-f[v][1][0]\)的最小值\(minn\),再设一个标记,如果有一个儿子取到了\(f[v][1][1]\),标记一下。如果到最后一直没有标记过,那么\(f[u][0][1]\)还得加上\(minn\)。意思是将一个儿子标记上,那么要减掉之前加上去的\(f[v][0][1]\),再加上\(f[v][1][1]\),选这样新产生贡献的最小\(v\)。
最后取\(f[1][0][1]\)和\(f[1][1][1]\)中较小的一个就行。
一直卡在90分上过不了的原因:
认真看题!!!
竟然还有90分,出题人真良心。
#include#include #include #include using namespace std;int n,f[1505][2][2],ans;// 2-> 0 1 表示i能不能被覆盖 int head[1505],tot,w[1505];struct edge{ int node,next;}e[3005];void add(int x,int y){ e[++tot].node=y; e[tot].next =head[x]; head[x]=tot;}void dfs(int u,int fa){ f[u][1][1]=w[u]; bool flag=0; int minn=0x7ffffff; for(int i=head[u];i;i=e[i].next) { int v=e[i].node; if(v==fa) continue; dfs(v,u); /* f[u][0][0]=min(f[u][0][0],f[v][0][1]); f[u][0][1]=min(f[u][0][1],f[v][1][1]); f[u][1][1]=min(f[u][1][1],min(f[v][0][0],min(f[v][0][1],f[v][1][1]))+w[u]); minn=min(minn,f[v][1][1]);(水平倒退www)*/ f[u][0][0]+=min(f[v][0][1],f[v][1][1]); minn=min(minn,f[v][1][1]-f[v][0][1]); if(f[v][1][1]>f[v][0][1]) f[u][0][1]+=f[v][0][1]; else f[u][0][1]+=f[v][1][1],flag=1; f[u][1][1]+=min(f[v][1][1],min(f[v][0][1],f[v][0][0])); } /* f[u][0][1]=min(f[u][0][1],minn); if(!flag) f[u][0][0]=0,f[u][1][1]=w[u]; */ //只要儿子中有一个安排了保安,u就会被覆盖到 //如果儿子中都没有安排保安,那么就选一个替换 if(!flag) f[u][0][1]+=minn; }int main(){// memset(f,0x7f,sizeof(f)); scanf("%d",&n); int x,y,k; for(int i=1;i<=n;++i) { scanf("%d",&x); scanf("%d%d",&w[x],&k); for(int j=1;j<=k;++j) { scanf("%d",&y); add(x,y); add(y,x); } } dfs(1,0); ans=min(f[1][1][1],f[1][0][1]); printf("%d\n",ans); return 0;}