1 条题解

  • 0
    @ 2025-10-8 16:49:15
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=1600;
    vector<int>G[N];
    LL f[N][2][2],w[N];
    /*
        这里的  安全 表示以x为根的子树全部都安全
              不安全 表示以x为根的子树除了x都安全
        f[x][0][0]表示 x这个点不安全,不安装监控,   
        f[x][0][1]表示 x这个点不安全,   安装监控,   ———很明显不合理所以去除 
        f[x][1][0]表示 x这个点安全  ,不安装监控,   
        f[x][1][1]表示 x这个点安全  ,   安装监控,   
         
    */
    void dp(int x)
    {
    	f[x][0][0]=0;
    	//f[x][0][1]=w[x];
    	f[x][1][0]=0;
    	f[x][1][1]=w[x];
    	LL t=(LL)1<<40;
    	for(int y:G[x])
    	{
    		dp(y);
    		//1
    		f[x][0][0]+=f[y][1][0];
    		//2
    		//f[x][0][1]=
    		//3
    		f[x][1][0]+=min(f[y][1][0],f[y][1][1]);
    		t=min(t,f[y][1][1]-f[y][1][0]);
    		//4
    		f[x][1][1]+=min(f[y][0][0],min(f[y][1][0],f[y][1][1]));
    	}
    	if(t>0) f[x][1][0]+=t;
    	
    }
    int main()
    {
    	int n;scanf("%d",&n);
    	int rt=(n+1)*n/2;
    	for(int i=1;i<=n;i++)
    	{
    		int x;scanf("%d",&x);
    		scanf("%lld",&w[x]);
    		int m;scanf("%d",&m);
    		for(int j=1;j<=m;j++)
    		{
    			int y;scanf("%d",&y);
    			G[x].emplace_back(y);rt-=y;
    		}
    	}
    	dp(rt);
    	printf("%lld",min(f[rt][1][0],f[rt][1][1]));
    	return 0;
    }
    
    • 1

    *【树形DP:相邻点兼容】保护所有点[SDOI2006] 保安站岗

    信息

    ID
    303
    时间
    1000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    305
    已通过
    59
    上传者