树形DP

二叉苹果树


思路

  • $dp[u][j表示节点u留下j条边的最大价值,每一次决策只有三种情况:剪左子树,剪右子树,两个都不剪
  • 剪左边:$dp[u][j]=dp[rson][j-1]+v[rson]$,同理,剪右边:$dp[u][j]=dp[lson][j-1]+v[lson]$
  • 两边都不剪:$dp[u][j]=dp[lson][j]+dp[rson][k-j-2]$

代码:记忆化搜索

int f[N][N];
bool t[N][N];
int dp(int u,int k)
{
if(t[u][k]) return f[u][k];
t[u][k]=1;
if(!k) return f[u][k]=0;
int tmp1=dp(lson[u],k-1)+v[sonl[u]];
int tmp2=dp(rson[u],k-1)+v[sonr[u]];
int tmp3=0;
for(int l=0;l<k-2;l++)
tmp3=max(tmp3,dp(lson[u],l)+dp(rson[u],k-l-2));
return f[u][k]=max(tmp1,max(tmp2,tmp3+lson[u]+rson[u]));
}

高精度模板

高精度模板

济南Day3 坐标型动态规划及背包

花店橱窗布置


思路

  • $f[i][j]$表示前i个花瓶前j个花束的最大美学价值
  • $f[i][j]=max(f[i-1][k],f[i][j])$

当然还有另外一种思路(太强了!!!):

  • 整张表都是向右下方走的,向下走加上数值,向右走无影响
  • 如果向下走代表花束放入花瓶,向右走无影响代表不放入
int f[N][N],mp[N][N];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j]+mp[i][j],f[i][j-1]);

矩阵取数


思路

  • 因为每次取头和尾,所以一定是一个连续的区间
  • $f[i][j]$表示从i取到j的最大得分
  • $f[i][j]=max(f[i][j-1]+a[j]2^(i-1+n-j+1+1) \ , \ f[i-1][j]+a[i]2^(i-1+n-j+1+1))$
  • 指数是轮数,当前数前面有多少个数被取走,就有多少轮,注意一下1的问题
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×