鱼肉炸弹
Description
舒克和贝塔终于下定决心要去营救被关押在众猫聚居的A城中的大米同志。
A城的构造是很奇怪的。A城中的所有N栋建筑沿着一条直线排列，而且没有两栋楼的高度是相同的。而大米同志就被关押在其中的某栋建筑中。每一栋建筑的顶上都是有一些猫们在看守的。如果按照从一端到另一端的顺序将所有的建筑编号为1到N,那么第i栋建筑的高度为Hi，顶上的猫的数量为Ci.
每一只猫不但可以看守住其所在建筑的楼顶,还可以看守住一些比它所在建筑要低的楼的楼顶。前提是没有被其他楼所挡住。A城中的建筑都是很高的,高到可以忽略它们之间的距离和它们的水平面面积。于是可以认为，楼i上的猫能看守楼j的楼顶，当且仅当楼i的高度不低于楼j，且楼i到楼j之间的所有楼房的高度都低于楼i。
现在,神勇的贝塔同学已经潜入了A城内部营救大米同志，而舒克则负责驾驶直升机提供空中支援。按照约定，贝塔找到并救出大米后会爬上楼顶施放信号让舒克前来接应。
舒克的飞机上装备有K枚鱼肉炸弹。每一枚鱼肉炸弹都可以在被投放到某一座楼的楼顶一段时间之后使该楼所有猫丧失行动能力。由于舒克并不知道贝塔会登上哪座楼的楼顶，所以现在他决定减少在最坏情况下与贝塔汇合时被发现的可能。具体来说，假设第i栋楼被Si只猫看守（注意Si只猫包括该楼上的Ci只猫以及其他楼上所有能看守该楼顶的猫)，他希望使用这K枚炸弹使得Si中的最大值最小。聪明的舒克很快就通过正确地选择炸弹投放地点完成了一这目标。你能吗？
Input
第一行有两个整数N和K。
第二行至第N+1行每行有两个整数，依次为编号为1的楼到编号为N的楼的高度(Hi)和楼顶的猫数(Ci)。
数据规模:
1<=N<=100000
1<=K<=5
1<=Hi<=1000000000
0<=Ci<=1000000000
Output
在这个题目中，你只需输出一个整数，表示使用K枚炸弹所能达到的Si中的最大值最小能是多少。
Sample Input
样例1
3 2
1 2
3 1
2 2
样例2
3 1
1 2
3 1
2 2
样例3
5 1
1 4
5 1
3 4
4 2
2 5
Sample Output
样例1
1
(说明:可投放在第一座楼和第三座楼上)
样例2
2
(说明:可投放在第二座楼上)
样例3
6
(说明:可投放在第四座楼上)
解题思路
这题就是一个树形dp题
首先，我们要建树（用一个伪二分）
一段中最大的数为根，根左边的数为是左子树，右边为右子树
long long maketree(long long l,long long r)
{
if(l>r)return 0;//特判
if(l==r)return l;
long long o=0,mid=0;
for(long long i=l;i<=r;i++)//找最大数
if(h[i]>o)
{
o=h[i];
mid=i;//标记
}
a[mid].l=maketree(l,mid-1);//左子树
a[mid].r=maketree(mid+1,r);//右子树
return mid;//返回
}
经过这个代码处理
样例三为
5
/ \
1 4
/ \
3 2
仔细看
根是不是可以看到它的所有子树
这就是这样建树的妙
然后用一个f[x][i+j]
表示为 x点 左子树的炸弹数+右子树的炸弹数，最小的最大值
void dfs(long long x)//搜索
{
b[x]=1;//标记
if(b[a[x].l]==0)dfs(a[x].l);//左子树（递归）
if(b[a[x].r]==0)dfs(a[x].r);//右子树
for(long long i=0;i<=k;i++)//枚举
for(long long j=0;j<=k-i;j++)
{
f[x][i+j]=min(f[x][i+j],max(f[a[x].l][i],f[a[x].r][j])+c[x]);//状态转移（自己摸索）
if(i+j+1<=k)
f[x][i+j+1]=min(f[x][i+j+1],max(f[a[x].l][i],f[a[x].r][j]));
}
}
下面呈上AC代码，用来对拍
AC代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
long long n,k,BOSS,h[1000005],c[1000005],b[1000005],f[1000005][6];
struct node
{
long long l,r;
}a[1000005];
long long maketree(long long l,long long r)
{
if(l>r)return 0;//特判
if(l==r)return l;
long long o=0,mid=0;
for(long long i=l;i<=r;i++)//找最大数
if(h[i]>o)
{
o=h[i];
mid=i;//标记
}
a[mid].l=maketree(l,mid-1);//左子树
a[mid].r=maketree(mid+1,r);//右子树
return mid;//返回
}
void dfs(long long x)//搜索
{
b[x]=1;//标记
if(b[a[x].l]==0)dfs(a[x].l);//左子树（递归）
if(b[a[x].r]==0)dfs(a[x].r);//右子树
for(long long i=0;i<=k;i++)//枚举
for(long long j=0;j<=k-i;j++)
{
f[x][i+j]=min(f[x][i+j],max(f[a[x].l][i],f[a[x].r][j])+c[x]);//状态转移（自己摸索）
if(i+j+1<=k)
f[x][i+j+1]=min(f[x][i+j+1],max(f[a[x].l][i],f[a[x].r][j]));
}
}
int main()
{
memset(f,0x3f,sizeof(f));//初值
f[0][0]=0;
scanf("%lld%lld",&n,&k);//用long long 会炸
for(long long i=1;i<=n;i++)scanf("%lld%lld",&h[i],&c[i]);
BOSS=maketree(1,n);//建树，找根
dfs(BOSS);//dfs
cout<<f[BOSS][k];//输出
}
京公网安备 11010502036488号