AT_abc364_e [ABC364E] Maximum Glutton

Posted on Edited on In ,

前情

当场没做 D 来做 E 是明智的，D 根本想不到的。

题目

翻译一下：

高桥准备 \(n\) 个菜，每个菜肴有甜味值 \(a_i\) 和 咸味值 \(b_i\)。高桥可以按任意顺序排放这些菜肴。Snuke 按排放的顺序吃，当吃的总甜味值大于 \(X\) 或总咸味值大于 \(Y\) 时停止。求吃的菜肴总数的最大值。

思路

Step 1

这道题和 C 题如出一辙，但仔细一看发现未必。这题求的是最大值。

数据范围是 \(n\le 80\) 且 \(X,Y\le 1000\) 显然 dp。

对比 P2240 和 P1048，发现其实和分别这次 C 题和 E 题道理相同。

一眼类似于背包的 dp，不难设计状态转移：

\(dp(i,x,y)=\max\{dp(i+1,x,y),1+dp(i+1,x-a_i,y-b_i)\}\)。

其中 \(i\) 表示考虑了前 \(i\) 个菜肴，\(x,y\) 分别表示能承受的甜味、咸味值还剩余多少，\(t\) 表示已经选了 \(t\) 个菜肴。

事实上，\(x\) 确定了 \(y\) 就确定了，故记忆化时忽略 \(y\)。否则空间肯定开不下。代码中的 cnt 是为了方便编写，实则不必计入状态。

同时不难写出类似于这样的代码（读者别急着写类似于这样的代码）：

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
47
48
49
50
51
52
// 赛时代码
// #define EXT
#include <bits/stdc++.h>
#ifdef EXT
    #include <bits/extc++.h>
#endif

#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 i128;

const int INF=1<<29;
const ll INFL=1ll<59;

const int N=114;
const int M=10024;

int n,x,y;
int a[N],b[N];
int mem[N][M][N];

inline int dp(int d,int xx,int yy,int cnt)
{
    if(xx<0||yy<0) return cnt;
    if(d==n+1) return cnt;
    int& ans=mem[d][xx][cnt];
    if(ans!=-1) return ans;
    int ans0=0,ans1=0;
    ans0=dp(d+1,xx-a[d],yy-b[d],cnt+1);
    ans1=dp(d+1,xx,yy,cnt);
    return ans=max(ans0,ans1);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("in.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    memset(mem,-1,sizeof(mem));
    cin>>n>>x>>y;
    rep(i,1,n) cin>>a[i]>>b[i];
    cout<<dp(1,x,y,0);
}

同：https://atcoder.jp/contests/abc364/submissions/56045157

很可惜，这样的思路是有漏洞的！

Step 2

比赛的时候碰到这种情况一定冷静！

显然，该程序并未考虑顺序问题。

0-1 背包中物体选的顺序是不考虑的。但题目中特别说了：

高桥可以按任意顺序排放这些菜肴。

反例：不妨只考虑甜味值，假设咸味值远远还没有达到极限。假设选的菜肴中有一个菜的甜味值为 \(p\)，另一个在它之前的菜肴甜味值为 \(q\)。假设除去这两个菜肴以外已经选了甜味值 \(m\)，且 \(m+p+q>m+q>X>m+p>m\)。

按照我们之前的方案，最大的甜味值被认为是 \(m+q\)。然而将 \(p\) 和 \(q\) 交换就得到最大甜味值 \(m+p+q\)，所以最大的菜肴数也比原来多 \(1\)，故原方法有漏洞。

很容易想到用排序法修复 Bug。

Step 3

这是我们将咸味值加进来。我们不妨只考虑其中两个临项 \(i\) 和 \(i+1\) 的情况。列表得：

项（菜） 已选甜味 已选咸味
\([1,i)\) \(x\) \(y\)
\(i\) \(x+a_i\) \(y+b_i\)
\(i+1\) \(x+a_i+a_{i+1}\) \(y+b_i+b_{i+1}\)

反之：

项（菜） 已选甜味 已选咸味
\([1,i)\) \(x\) \(y\)
\(i\) \(x+a_{i+1}\) \(y+b_{i+1}\)
\(i+1\) \(x+a_i+a_{i+1}\) \(y+b_i+b_{i+1}\)

若 \(x+a_{i+1}>X>x+a_{i}\) 且 \(y+b_{i+1}>Y>y+b_{i}\) 这时一定有 \(a_{i+1}+b_{i+1}>a_{i}+b_{i}\)。也就是说，符合条件的满足：\(a_{i+1}+b_{i+1}>a_{i}+b_{i}\)。那我们可以将 \(a_i+b_i\) 从小到大排序。

补充：不妨考虑满足 \(x+a_{i+1}>X>x+a_{i}\) 但不满足 \(y+b_{i+1}>Y>y+b_{i}\)，这时交换后会出现和交换前一样的现象。

在基础上改一下就可以得到：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 赛时代码修改
// #define EXT
#include <bits/stdc++.h>
#ifdef EXT
    #include <bits/extc++.h>
#endif

#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 i128;

const int INF=1<<29;
const ll INFL=1ll<59;

const int N=114;
const int M=10024;

int n,x,y;
vector<pair<int,int> > s;
int a[N],b[N];
int mem[N][M][N];

int cmp2(pair<int,int> A,pair<int,int> B)
{
    return A.second+A.first<B.first+B.second;
}

inline int dp(int d,int xx,int yy,int cnt)
{
    if(d==n+1) return cnt;
    int& ans=mem[d][xx][cnt];
    if(ans!=-1) return ans;
    int ans0=0,ans1=0;
    if(xx>=a[d]&&yy>=b[d]) ans0=dp(d+1,xx-a[d],yy-b[d],cnt+1);
    else ans0=cnt+1;
    ans1=dp(d+1,xx,yy,cnt);
    return ans=max(ans0,ans1);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("in.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    memset(mem,-1,sizeof(mem));
    cin>>n>>x>>y;
    rep(i,1,n){int ai,bi;cin>>ai>>bi;s.push_back({ai,bi});}
    sort(s.begin(),s.end(),cmp2);
    for(int i=0;i<s.size();++i) a[i+1]=s[i].first,b[i+1]=s[i].second;
    int ans=dp(1,x,y,0);
    cout<<ans;
}

代码中 mem 数组中 cnt 的维度同样可以略去不计。

总结

当场肯定不能像写题解一样考虑，一般来说是用直觉做的（也有一眼看穿证明的）。

这个思路阶梯是我当场真实体验。所以希望大家考虑全面。

但是本题解给出的方法只是思考的时候用的，并不是证明。有疑问或证明欢迎评论！

难度评级：绿或蓝。