Description
有一些宫殿,它们呈树形结构,相邻的宫殿之间可以互相望见.在一些宫殿设立士兵,使得所有的宫殿都有士兵或是被士兵望见.求最小士兵数.
Sol
状态：
f[x][0] 表示结点i被父结点覆盖,以i为根的树需要的最小士兵数
f[x][1] 表示结点i被自己覆盖,以i为根的树需要的最小士兵数
f[x][2] 表示结点i被子结点覆盖,以i为根的树需要的最小士兵数
转移：(y是x的子结点)
f[x][0]=Σmin(f[y][1],f[y][2])
f[x][1]=Σmin(f[y][1],f[y][2],f[y][3])
f[x][2]=Σmin(f[y][1],f[y][2])+d,d=min(f[y][1]-min(f[y][1],f[y][2]))
就f[x][2]的转移稍微难想一点点,可以这样理解:
先算f[x][2]=Σmin(f[y][1],f[y][2]),但是这样并不能保证一定在某个y上设立了士兵
如果要保证这一点,那么就可能产生附加的代价,就是f[y][1]-min(f[y][1],f[y][2]),加上最小代价即可
Code
1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 #define Rg register 5 #define il inline 6 #define inf 2100000000 7 #define go(i,a,b) for(Rg int i=a;i<=b;++i) 8 using namespace std; 9 il int read() 10 { 11 int x=0,y=1;char c=getchar(); 12 while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} 13 while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();} 14 return x*y; 15 } 16 const int N=1501; 17 int n,rt,f[N][3],a[N]; 18 vector<int> c[N]; 19 bool d[N]; 20 il void dp(int x) 21 { 22 f[x][1]=a[x]; 23 int hhh=c[x].size()-1,t=inf; 24 if(hhh<0)return; 25 f[x][2]=0; 26 go(i,0,hhh) 27 { 28 int y=c[x][i];dp(y); 29 f[x][0]+=min(f[y][1],f[y][2]); 30 f[x][1]+=min(f[y][0],min(f[y][1],f[y][2])); 31 t=min(t,f[y][1]-min(f[y][1],f[y][2])); 32 } 33 f[x][2]=f[x][0]+t; 34 } 35 int main() 36 { 37 n=read(); 38 go(i,1,n) 39 { 40 int t=read(),m,x; 41 a[t]=read();m=read(); 42 while(m--){x=read();c[t].push_back(x);d[x]=1;} 43 } 44 go(i,1,n)f[i][2]=inf; 45 go(i,1,n)if(!d[i]){rt=i;break;} 46 dp(rt); 47 printf("%d ",min(f[rt][1],f[rt][2])); 48 return 0; 49 }