首页 > 代码库 > HDU4044 GeoDefense
HDU4044 GeoDefense
题解:
树形dp + 分组背包(两个阶段)
具体解释见代码
代码:
#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 = 1010; const int maxm = 205; const int INF = 1e9; int T, n, m; int dp1[ maxn ][ maxm ], dp2[ maxn ][ maxm ]; int attack[ maxn ][ maxm ], num[ maxn ]; //dp1[ u ][ j ]表示u节点不放攻击点,给予费用为j时,其儿子的最小防御值 //dp2[ u ][ j ]表示u节点放或不放攻击点,给予费用为j时,u包括其儿子最小防御值 //动态规划有2步,第一步是求dp1, 然后在dp1的基础上求得dp2 //在dp过程中,因为价格可能为0,所以不能直接用逆向,否则无法保证只能放一个攻击点,需要一个变量t存储 //优化一下攻击方式,attack[ i ][ j ]表示i节点在给予费用为j时的最大攻击力,这样省去很多时间和步骤 struct Edge { int nxt, v; }edge[ maxn * 2 ]; int head[ maxn * 2 ], cnt; void init() { memset( head, -1, sizeof( head ) ); cnt = 0; } void addEdge( int u, int v ) { edge[ cnt ].v = v; edge[ cnt ].nxt = head[ u ]; head[ u ] = cnt ++; } void dfs( int u ,int fa ) { if( head[ u ] == -1 || ( edge[ head[ u ] ].v == fa && edge[ head[ u ] ].nxt == -1 ) ) { for( int i = 0; i <= m; i ++ ) dp2[ u ][ i ] = attack[ u ][ i ]; return ; } for( int i = 0; i <= m; i ++ ) dp1[ u ][ i ] = INF; for( int i = head[ u ]; i != -1; i = edge[ i ].nxt ) { int v = edge[ i ].v; if( v == fa ) continue; dfs( v, u ); for( int j = m; j >= 0; j -- ) { int t = 0; for( int k = 0; k <= j; k ++ ) { t = max( t, min( dp1[ u ][ j - k ], dp2[ v ][ k ] ) ); } dp1[ u ][ j ]= t; } } for( int j = m; j >= 0; j -- ) { int t = 0; for( int k = 0; k <= j; k ++ ) { t = max( t, dp1[ u ][ j - k ] + attack[ u ][ k ] ); } dp2[ u ][ j ] = t; } } int main() { scanf( "%d", &T ); while( T -- ) { scanf( "%d", &n ); init(); memset( attack, 0, sizeof( attack ) ); for( int i = 1; i < n; i ++ ) { int x, y; scanf( "%d%d", &x, &y ); addEdge( x, y ); addEdge( y, x ); } scanf( "%d", &m ); for( int i = 1; i <= n; i ++ ) { scanf( "%d", &num[ i ] ); int pri, pow; for( int j = 0; j < num[ i ]; j ++ ) { scanf( "%d%d", &pri, &pow ); attack[ i ][ pri ] = max( attack[ i ][ pri ], pow ); } } for( int i = 1; i <= n; i ++ ) for( int j = 1; j <= m; j ++ ) attack[ i ][ j ] = max( attack[ i ][ j ], attack[ i ][ j - 1 ] ); dfs( 1, -1 ); printf( "%d\n", dp2[ 1 ][ m ] ); } return 0; }
HDU4044 GeoDefense
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。