Bzoj 1899(贪心+DP)

BZOJ 1899
题意:见上。
本题无法直接 DP,所以我们想到贪心方案,吃饭慢的排前面打饭,按照这个方法来进行排序后就可以DP了。
可以设$dp(i,j)$为前$i$个人在1号打饭花了$j$时间的最小吃饭时间。
转移:
$i$安排到1号:$dp(i,j)=max(dp(i-1,j-a_i),j+b_i)$
$i$安排到2号:$dp(i,j)=max(dp(i-1,j),sum_i-j+b_i)$
其中$sum_i=\sum_{j=1}^ia_j$
初值$dp(0,0)=0$,其他为$INF$
知识点:这种无法直接DP也无法直接贪心的题目可以贪心后DP做,并且如果DP的维度太大需要根据性质尝试合并维度或者删除维度。

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
45
46
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 200 + 5, INF_ = 1000000000;
struct data {
int a, b;
}pp[MAXN];
int n, dp[MAXN][MAXN * MAXN], sum[MAXN];
bool cmp(const data &x, const data &y) {return x.b > y.b;}
void clean() {
sum[0] = 0;
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d%d", &pp[i].a, &pp[i].b);
std::sort(pp + 1, pp + 1 + n, cmp);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + pp[i].a;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= sum[n]; j++) dp[i][j] = INF_;
dp[0][0] = 0;
int ans = INF_;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum[i]; j++) {
if (j >= pp[i].a) dp[i][j] = std::min(dp[i][j], std::max(dp[i - 1][j - pp[i].a], j + pp[i].b));
dp[i][j] = std::min(dp[i][j], std::max(dp[i - 1][j], sum[i] - j + pp[i].b));
if (i == n) ans = std::min(ans, dp[i][j]);
}
}
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------