备案网站公共查询系统,大连html5网站建设费用,仿牌网站安全,word怎么做网站链接这类题型在 dp 中很常见#xff0c;于是做一个总结吧#xff01;#xff01;#xff01;
最经典的题#xff1a;没有上司的舞会
传送门#xff1a;没有上司的舞会 - 洛谷
状态表示#xff1a;
dp[i][0] 为 以 i 为根的子树中#xff0c;选择 i 节点的最大欢乐值
d…这类题型在 dp 中很常见于是做一个总结吧
最经典的题没有上司的舞会
传送门没有上司的舞会 - 洛谷
状态表示
dp[i][0] 为 以 i 为根的子树中选择 i 节点的最大欢乐值
dp[i][1] 为 以 i 为根的子树中不选择 i 节点的最大欢乐值
状态转移方程 dp[i][0] dp[[j][1] dp[i][1] dp[j][0] j 为 i 的子节点
AC代码
#includebits/stdc.h
using namespace std;
#define int long long
const int N 6e3 10;
int a[N];
int h[N], e[N], ne[N], idx;
bool flag[N] { 0 };
int f[N][2];
void add(int a, int b)
{e[idx] b;ne[idx] h[a];h[a] idx;
}
void dfs(int u , int fa ) // 树形 dp 中一般都是用 dfs
{for (int i h[u]; i ! -1; i ne[i]){int j e[i];dfs(j, u);f[u][0] max(f[j][0] , f[j][1] );f[u][1] f[j][0];}
}
void solve()
{memset(h, -1, sizeof h);int n; cin n;for (int i 1; i n; i) cin a[i];for (int i 1; i n; i){int a, b;cin a b;add(b, a);flag[a] true;}int root -1;for (int i 1; i n; i){f[i][1] a[i];if (!flag[i]) root i;}dfs(root, -1 );cout max (f[root][1], f[root][0]) endl;
}
signed main()
{int tt 1;while (tt--)solve();return 0;
}
再来一道经典题目选课 树形dp 点
传送门[CTSC1997] 选课 - 洛谷
状态表示
dp[i][[j] 以 i 为根的子树中选择 j 个节点的最大学分
状态转移方程 dp[i][j] dp[i][j - k] dp[t][k] t 为 j 的子节点 k 是从子树中选择 k 个节点
注意
1.你要统计子树中节点的个数
2. 需要假设一个虚拟源节点因此要把 m
AC代码
#includebits/stdc.h
using namespace std;
#define int long long
const int N 620;
int f[N][N]; int n, m;
int h[N], e[N], ne[N], idx, score[N];
int Size[N];
void add(int a, int b)
{e[idx] b; ne[idx] h[a]; h[a] idx;
}
void dfs(int u, int fa)
{Size[u] 1;f[u][1] score[u];for (int i h[u]; i ! -1; i ne[i]){int j e[i];if (j fa)continue;dfs(j, u);Size[u] Size[j];for (int t min(m, Size[u]); t; t--) // 注意 t 要从大到小遍历// 如果 t 要从小到大遍历就会导致当 t 变大时更新最新状态时会用到这个子树刚刚更新的状态{for (int k min(Size[j], t - 1); k 0; k--){f[u][t] max(f[u][t], f[u][t - k ] f[j][k] );}}}
}
signed main()
{memset(h, -1, sizeof h);cin n m;m;for (int i 1; i n; i){int x; cin x; add(i, x); add(x, i);cin score[i];}dfs(0, -1);cout f[0][m] endl;return 0;
}
经典题目二叉苹果树树形dp 边
传送门https://www.luogu.com.cn/problem/P2015
状态表示dp[i][j] 以 i 为根的子树中保留 j 条边的最多苹果树
这道题有一个隐含的条件当某条边被保留下来时从根节点到这条边的路径上的所有边也都必须保留下来
状态转移方程
dp[i][j] max( dp[i][j] , dp[i][j-k-1] dp[t][k] w[i] ) t 为子节点k是值子树中选择 k 条边
注意这个题要统计子树中边的条数
AC代码
#includebits/stdc.h
using namespace std;
const int N 220;
int f[N][N];
int h[N] , e[N] , ne[N] , idx , w[N];
int Size[N];
int n , m;
void add( int a , int b , int c )
{w[idx] c ; e[idx] b; ne[idx] h[a] ; h[a] idx;
}
void dfs( int u , int fa )
{for( int i h[u] ; i ! -1 ; i ne[i] ){int j e[i];if( j fa )continue;dfs( j , u );Size[u] Size[j] 1;for( int t min( Size[u] , m ) ; t ; t-- ){for( int k min(Size[j] , t - 1 ) ; k 0 ; k-- ){f[u][t] max( f[u][t] , f[u][t-k-1] f[j][k] w[i] );}}}
}
signed main()
{memset( h , -1 , sizeof h );cin n m;for( int i 0 ; i n - 1; i ){int a , b , c; cin a b c;add( a , b ,c );add( b , a , c );}dfs( 1 , -1 );cout f[1][m] endl;return 0;
}
