Fork me on GitHub

[贪心&DP][TJOI2013]拯救小矮人

贪心套DP呜呜呜

首先发现一个结论:一定是长得越矮的越靠上更优,因为如果一个大长腿的人在上先出去了,那么那一坨长得矮的人就会失去他们的垫脚石,所以为了要凑出这个大长腿的高度,一定要更多矮的人堆在一起,这显然不会更优,所以腿长的应该优先级靠后.
然后我们考虑胳膊的长度,我们发现,当两个人的腿长一样长时,那么胳膊短的排在胳膊长的人之前一定要更优.所以我们综合这两者考虑,我们对$A_i+B_i$为第一优先级,以$A_i$为第二优先级从小到大排序,然后我们考虑这个序列下应该选哪些小矮人出去更优.
因为每个人都有两个属性腿长和胳膊长,而且任意两个人如果最终都要出去,那么顺序无关.所以我们可以$DP$来解决这个问题,我们设$f[i][j]$来表示已经考虑了前$i$个人,出去了$j$个人时剩下的最高的高度,可以发现,如果出去了$j-1$个人并且$i$这个人的胳膊长度加上之前的最高的高度大于$h$,那么这个状态就可以用来转移状态,那么转移方程就很显然:

最后统计答案的时候,我们从高到低枚举出去了多少人,如果发现有一个$f[n][j]$被更新过,那么这个状态就可以更新最终的答案.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

const int N = 2005;

int n , h;
struct Node {
int Ai , Bi;
bool operator < ( const Node &x ) const {
if ( Ai + Bi == x.Ai + x.Bi )
return Ai < x.Ai;
else
return Ai + Bi < x.Ai + x.Bi;
}
} p[N];
int f[N];

int main ( void ) {
scanf ( "%d" , &n );
for ( int i = 1 ; i <= n ; i++ )
scanf ( "%d%d" , &p[i].Ai , &p[i].Bi );
scanf ( "%d" , &h );
memset ( f , -1 , sizeof ( f ) );
sort ( p + 1 , p + 1 + n );

// for ( int i = 1 ; i <= n ; i++ )
// printf ( "%d %d\n" , p[i].Ai , p[i].Bi );

f[0] = 0;

for ( int i = 1 ; i <= n ; i++ )
f[0] += p[i].Ai;
for ( int i = 1 ; i <= n ; i++ ) {
for ( int j = n ; j >= 1 ; j-- )
if ( f[j - 1] + p[i].Bi >= h )
f[j] = max ( f[j] , f[j - 1] - p[i].Ai );
}
for ( int i = n ; i >= 0 ; i-- )
if ( ~f[i] ) {
printf ( "%d\n" , i );
return 0;
}
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[贪心&DP][TJOI2013]拯救小矮人

文章作者:兮水XiShui丶

发布时间:2021年04月23日 - 10:04

最后更新:2021年04月23日 - 10:04

原始链接:http://krrrr.top/2021/04/23/贪心/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。