洛谷4
补题
这样想这道题目，对于每一个花盆，有选与不选两种操作，这不就是01背包吗。唯一的区别在于必须按照种类顺序去选花盆，每一种花盆的个数是有限制的。因此稍微改进01背包即可求解。
这位佬的博客讲的十分详细了。直接上代码了：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105, mod = 1000007;
int n, m, f[maxn], sum[maxn], a[maxn];
int main(){
cin >> n >> m;
for (int i = 1;i<=n;i++)cin>>a[i];
f[0] = 1;
for (int i = 0; i <= m;i++)
sum[i] = 1;
for (int i = 1; i <= n;i++){//外层枚举种类
for (int j = m; j >= 1;j--){//内层循环直接01背包
int t = j - min(a[i], j)-1;
if(t<0)
f[j] = (f[j] + sum[j - 1]) % mod;
else
f[j] = (f[j] + sum[j - 1] - sum[t] + mod) % mod;
}
for (int j = 1;j<=m;j++)
sum[j] = (sum[j - 1] + f[j]) % mod;
}
cout << f[m] << endl;
return 0;
} https://www.luogu.com.cn/problem/P1090 简单的算法题目，合并果子消耗的最小值显然等于,,,看错了，以为是区间dp，，，，结果一看就更简单了。。。直接合并数量小的，可以证明这样总体力最小。就一个贪心。。。。但是，
还有很多用排序，但是根本不测试就往上发那种一定会TLE代码的沙雕
于是发现multiset的插入删除只有log n的级别，那么我们的时间复杂度就一定是o(n)
#include <bits/stdc++.h>
using namespace std;
int main(){
multiset<int> heap;
int n;
cin>>n;
int x;
for (int i = 0; i < n;i++){
cin>>x;
heap.insert(x);
}
int sum1=0, sum=0;
for (int i = 1; i <= n - 1;i++){
sum1 = *heap.begin();
heap.erase(heap.begin());
sum1 += *heap.begin();
heap.erase(heap.begin());
sum += sum1;
heap.insert(sum1);
}
cout << sum << endl;
return 0;
} https://www.luogu.com.cn/problem/solution/P1091 从左到右和从右到左分别找就行
P1103书本整理，不是很理解https://www.luogu.com.cn/blog/user8742/solution-p1103
查看9道真题和解析
投递一汽大众等公司10个岗位 >
比亚迪成长空间 168人发布