第十三届蓝桥杯国赛 C++ B 组 J 题——搬砖（AC）

目录

• 1.搬砖
• • 1.题目描述
  • 2.输入格式
  • 3.输出格式
  • 4.样例输入
  • 5.样例输出
  • 6.数据范围
• 7.原题链接
• 2.解题思路
• 3.Ac_code

1.搬砖

1.题目描述

这天，小明在搬砖。

他一共有

n

n

n 块砖, 他发现第

i

i

i 砖的重量为

w

i

w_{i}

wi​, 价值为

v

i

v_{i}

vi​ 。他突然想从这些 砖中选一些出来从下到上堆成一座塔, 并且对于塔中的每一块砖来说, 它上面 所有砖的重量和不能超过它自身的价值。

他想知道这样堆成的塔的总价值（即塔中所有砖块的价值和）最大是多少。

2.输入格式

输入共

n

+

1

n+1

n+1 行, 第一行为一个正整数

n

n

n, 表示砖块的数量。后面

n

n

n 行, 每行两个正整数

w

i

,

v

i

w_i ,v_i

wi​,vi​

分别表示每块砖的重量和价值。

3.输出格式

一行, 一个整数表示答案。

4.样例输入

5

4 4

1 1

5 2

5 5

4 3

5.样例输出

10

6.数据范围

n

≤

1000

;

w

i

≤

20

;

v

i

≤

20000

。

n≤1000;w_i ≤20;v_i ≤20000 。

n≤1000;wi​≤20;vi​≤20000。

7.原题链接

搬砖

2.解题思路

诸如此题的模型，思路都是按照一种方式排序，使得最优解答案的选择情况，是排序后的一个子序列，然后直接进行背包

d

p

dp

dp 即可。

那么该如何去寻找排序的条件呢？一般的思路在于，对于砖块

x

x

x 和

y

y

y，如果排序后的结果

y

y

y 在

x

x

x的后面，那么对于任意

y

y

y 在

x

x

x 之上的摆放情况，都一定可以将两者调换。

如图，红色砖块为

y

y

y 上所有砖块的重量，我们设为

w

1

w_1

w1​，绿色为

x

x

x 与

y

y

y 之间的砖块重量，我们设为

w

2

w_2

w2​。

根据题意可知：

v

y

≥

w

1

，

v

x

≥

w

1

+

w

y

+

w

2

v_y≥ w_1，v_x≥w_1+w_y+w_2

vy​≥w1​，vx​≥w1​+wy​+w2​，1

假设排序后

y

y

y 在

x

x

x 的后面，那么也一定满足：

v

x

≥

w

1

，

v

y

≥

w

1

+

w

x

+

w

2

v_x≥ w_1，v_y≥w_1+w_x+w_2

vx​≥w1​，vy​≥w1​+wx​+w2​2

因为

v

x

≥

w

1

+

w

y

+

w

2

v_x≥w_1+w_y+w_2

vx​≥w1​+wy​+w2​1且

w

y

+

w

2

w_y+w_2

wy​+w2​一定大于

0

0

0，显然

v

x

≥

w

1

v_x≥ w_1

vx​≥w1​是一定符合要求的。

然后考虑第二个式子，因为

v

x

≥

w

1

+

w

y

+

w

2

v_x≥w_1+w_y+w_2

vx​≥w1​+wy​+w2​1，经过变形可得

v

x

−

w

y

≥

w

1

+

w

2

v_x-w_y≥w_1+w_2

vx​−wy​≥w1​+w2​3

将式子3带入式子2可得:

v

y

≥

w

x

+

v

x

−

w

y

v_y≥w_x+v_x-w_y

vy​≥wx​+vx​−wy​

将式子整理可得:

v

y

+

w

y

≥

w

x

+

v

x

v_y+w_y≥w_x+v_x

vy​+wy​≥wx​+vx​

由此，我们找到了排序条件，也就是说，当满足

v

y

+

w

y

≥

w

x

+

v

x

v_y+w_y≥w_x+v_x

vy​+wy​≥wx​+vx​ 时，任意

y

y

y 在

x

x

x 之上的摆放情况，都一定可以将两者调换

接下来就是进行背包

d

p

dp

dp即可，

定义

f

[

i

]

[

j

]

f[i][j]

f[i][j]为只考虑前

i

i

i 个物品，且选择的重量为

j

j

j 的最大价值。考虑如何进行转移，对于背包问题，无非是选与不选的两种抉择：

f

[

i

]

[

j

]

=

{

f

[

i

−

1

]

[

j

]

不可选

m

a

x

(

f

[

i

−

1

]

[

j

]

,

f

[

i

−

1

]

[

j

−

w

]

+

v

)

if j≥w且v≥j-w可选

f[i][j] = \begin{cases} f[i-1][j] &不可选\\ max(f[i-1][j],f[i-1][j-w]+v) &\text{if j≥w且v≥j-w} 可选\\ \end{cases}

f[i][j]={f[i−1][j]max(f[i−1][j],f[i−1][j−w]+v)​不可选if j≥w且v≥j-w可选​

题目体积最大只有2e4，答案即为从

f

[

n

]

[

0

]

f[n][0]

f[n][0]到

f

[

n

]

[

20000

]

f[n][20000]

f[n][20000]取个最大值。由于是01背包问题，可以使用滚动数组进行优化。

时间复杂度:

O

(

n

l

o

g

n

+

n

V

)

O(nlogn+nV)

O(nlogn+nV)

3.Ac_code

未优化版本：

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 1010;


int n;
//只考虑前 i 个砖块，且重量为 j 的最大价值
int f[N][N * 20];
PII a[N];
bool cmp(PII b, PII c) {
    return b.first + b.second < c.first + c.second;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++i) {
        int w = a[i].first, v = a[i].second;
        for (int j = 0; j <= 20000; ++j) {
            f[i][j] = f[i - 1][j];
            //可选情况
            if (w = j - w) f[i][j] = max(f[i][j], f[i - 1][j - w] + v);
        }
    }
    int ans=0;
    for(int i=0;i<=20000;++i) ans=max(ans,f[n][i]);
    cout << ans << '\n';
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

滚动数组优化：

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 1010;


int n;
//只考虑前 i 个砖块，且重量为 j 的最大价值
int f[N * 20];
PII a[N];
bool cmp(PII b, PII c) {
    return b.first + b.second < c.first + c.second;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++i) {
        int w = a[i].first, v = a[i].second;
        for (int j = 20000; j >= w; --j) {
            //可选情况
            if ( v >= j - w) f[j] = max(f[j], f[j - w] + v);
        }
    }
    int ans = 0;
    for (int i = 0; i <= 20000; ++i) ans = max(ans, f[i]);
    cout << ans << '\n';
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}