首页 > 代码库 > UVALive 2038 Strategic game
UVALive 2038 Strategic game
题解:
基础树形dp
dp[u][0] 表示不选u.那么子节点v都要选
dp[u][1]表示选择u,那么子节点v可选可不选
代码:
#include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define se second #define fs first #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define pii pair<int,int> #define ll long long const int maxn = 1600; int dp[ maxn ][ 2 ]; int n; int head[ maxn * 2 ], cnt; struct Edge { int u, v, nxt; }edge[ maxn * 2 ]; void addedge( int u, int v ) { edge[ cnt ].u = u; edge[ cnt ].v = v; edge[ cnt ].nxt = head[ u ]; head[ u ] = cnt ++; } void init() { cnt = 0; memset( head, -1, sizeof( head ) ); } void dfs( int u, int fa ) { dp[ u ][ 1 ] = 1; dp[ u ][ 0 ] = 0; for( int i = head[ u ]; i != -1; i = edge[ i ].nxt ) { int v = edge[ i ].v; if( v == fa ) continue; dfs( v, u ); dp[ u ][ 1 ] += min( dp[ v ][ 1 ], dp[ v ][ 0 ] ); dp[ u ][ 0 ] += dp[ v ][ 1 ]; } } int main() { while( ~scanf( "%d", &n ) ) { init(); while( n ) { int u, v, num; scanf( "%d:(%d)", &u, &num ); for( int i = 1; i <= num; i ++ ) { scanf( "%d", &v ); addedge( u, v ); addedge( v, u ); } n --; } dfs( 0, -1 ); printf( "%d\n", min( dp[ 0 ][ 0 ], dp[ 0 ][ 1 ] ) ); } return 0; }
UVALive 2038 Strategic game
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。