本文主要是介绍洛谷 Shaass and Bookshelf，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题其实是01背包问题的变形。
思路：我们看到，题目中并没有明说里面有什么限制，但我们可以推出来几个结论：
1.上层的书的宽度总和<=下层的书的总厚度
2.书架的长度并不会超过所有书的总厚度
我们可以这样转化一下问题：假如说我们已经规定了书架的长度容量，然后我们在下层去放书，接下来判断下层的厚度之和是不是要大于上层的宽度之和。相反，我们也可以上层放书，然后判断下层是否成立上面那个条件。这里选择前者进行谈论。
结论上也说了，书架的长度并不会超过所有书的厚度。所以我们可以从这个临界值开始递减求值。
由于数据范围上给的是200，所以我们直接用200了，这样就可以存储所有的可能性了，也不用适时更新了。接下来就是背包问题的模板了，把宽度当作价值，把厚度当作容量，这个时候的状态方程数组f就是代表i个厚度的时候最多能放多少宽度。
这样递推完毕之后，也就是说，我们已经选择了宽度最大的一批书放在了下层，而且厚度也够，这个时候我们还需要判断剩下的书里面的宽度总和是否小于等于厚度，判断是，那么就输出结束就行了。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<set>
#define int long long
#define MAX 1005
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII=pair<int, int>;
int n, m;
int counts;
int t[MAX];
int w[MAX];
int f[MAX];
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n;int sum = 0;for (int i = 1; i <= 200; i++)f[i] = -1e5;for (int i = 1; i <= n; i++) {cin >> t[i] >> w[i];for (int j = 200; j >= t[i]; j--) {f[j] = max(f[j], f[j - t[i]] + w[i]);}sum += w[i];}for (int i = 1; i <= 200; i++) {if (sum - f[i] <= i) {cout << i;break;}}return 0;
}这篇关于洛谷 Shaass and Bookshelf的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
