#树形dp#JZOJ 1087 鱼肉炸弹

本文主要是介绍#树形dp#JZOJ 1087 鱼肉炸弹，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

有n栋楼房，两栋楼房可以看见当且仅当中间的楼房不高于两栋楼房，使用炸弹可破坏某一栋楼房，问使用K枚炸弹使得能看见楼房i的楼房数的最大值最小。

---

分析

树形dp，容易得出
$f[x][i+j]=min(f[x][i+j],max(f[l][i],f[r][j])+b[x])$
$f[x][i+j+1]=min(f[x][i+j+1],max(f[l][i],f[r][j]))$

---

代码

#include <cstdio>
#include <cctype>
#include <cstring>
#define N 100000
using namespace std;
typedef long long ll;
int n,m,a[N+1],b[N+1],le[N+1],ri[N+1]; ll f[N+1][7];
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int build(int l,int r){if (l==r) return l;int s1=0,s;for (int i=l;i<=r;i++)if (s1<a[i]) s1=a[i],s=i;if (s>l) le[s]=build(l,s-1); //确定左边if (s<r) ri[s]=build(s+1,r);//确定右边return s;
}
ll min(ll a,ll b){return (a<b)?a:b;}
ll max(ll a,ll b){return (a>b)?a:b;}
void dp(int x){if (!x) return;int l=le[x],r=ri[x];dp(le[x]); dp(ri[x]);for (int i=0;i<=m;i++)for (int j=0;j<=m-i;j++){f[x][i+j]=min(f[x][i+j],max(f[l][i],f[r][j])+b[x]);//dpif (i+j<m) f[x][i+j+1]=min(f[x][i+j+1],max(f[l][i],f[r][j]));}
}
int main(){n=in(); m=in(); memset(f,127,sizeof(f));for (int i=1;i<=n;i++) a[i]=in(),b[i]=in();int root=build(1,n); f[0][0]=0; dp(root);return !printf("%lld",f[root][m]);
}

这篇关于#树形dp#JZOJ 1087 鱼肉炸弹的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---