本次训练题目为背包及线段树。
1.5732: 装箱问题
NOIP2001普及组 T4
比较经典的01背包，我们可以他的花费和价值相同，放下的东西越多，剩下的东西就越少
#include <bits/stdc++.h>
using namespace std;
const int M = 20005;
int dp[M];
int main()
{
int m, n;
cin >> m >> n;
for (int i = 0; i < n; i++)
{
int w;
cin >> w;
for (int j = m; j >= w; j--)
dp[j] = max(dp[j], dp[j - w] + w);
}
cout << m - dp[m] << "
";
return 0;
}
2.4848: 开心的金明
NOIP2006普及组 T2
同样为背包，价值为容量乘上体积。
#include <bits/stdc++.h>
using namespace std;
const int M = 30005;
int dp[M];
int main()
{
int m, n;
cin >> m >> n;
for (int i = 0; i < n; i++)
{
int w, c;
cin >> w >> c;
for (int j = m; j >= w; j--)
dp[j] = max(dp[j], dp[j - w] + w * c);
}
cout << dp[m] << "
";
return 0;
}
3.5992: 图书管理员
NOIP2017普及组 T2
这题不是这次训练的内容，可以使用模拟，但是还是比较容易超时的。
对于每一位读者，求出他所需要的书中图书编码最小的那本书，这个题目查询还是比较多的，我们可以直接排序。
每本书对10^需求码的长度取余得到的就是需求码，和自己的一样就可以输出了。
#include <bits/stdc++.h>
using namespace std;
int n, m, x, t, k, ans, a[1005];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
while (m--)
{
cin>>x>>k;
ans = -1, t = 1;
while (x)
x--, t *= 10;
for (int i = 0; i < n; i++)
if (k == a[i] % t)
{
ans = a[i];
break;
}
printf("%d
", ans);
}
return 0;
}
4.6028: 买铅笔
NOIP2016普及组 T1
一看题目你是不是以为是背包啊，肯定不是啊，只买一个包装，只要算出每种包装需要花的钱就可以了。
只买一种包装的，所以只要算出每种包装需要花的钱就可以了。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int ans = 1e9;
for (int i = 0; i < 3; i++)
{
int a, b;
cin >> a >> b;
int t = ceil(n * 1.0 / a) * b;
ans = min(t, ans);
}
cout<<ans;
return 0;
}
5.5912: 货币系统
NOIP2018提高组Day1T2
思路：
1、将a数组从小到大排序
2、最小的数必须要选，然后利用完全背包的思想，从ai到最大值筛选一遍，将可以组成的打上标记
3、在判断后面的数字时，如果已经被标记过了，就不再选，没有被标记过就标记一下，再筛选一次数(即一次完全背包)
#include <bits/stdc++.h>
using namespace std;
int dp[25001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int cas;
cin>>cas;
while(cas--)
{
int a[101], n, mx = 0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mx = max(mx, a[i]);
}
sort(a+1, a+n+1);
memset(dp, 0, sizeof(dp));//默认不能
dp[0] = 1;//0能被任何货币表示
int res = 0;
for(int i=1;i<=n;i++)
{
if(dp[a[i]]==1)//判断过能的忽略
continue;
res++;//小的不能被大的兑换，因此a[i]不可能再被兑换
for(int j=a[i];j<=mx;j++)
{
dp[j] = dp[j] | dp[j-a[i]];//如果j已经能被兑换，或j-a[i]能被兑换，则j也能被兑换
}
}
cout<<res<<endl;
}
return 0;
}
6.4798: 金明的预算方案
NOIP2006提高组T2
只选主件、只选主件和第一个附件、只选主件和第二个附件、主件和两个附件都选这四种情况是互斥的，只能且必须任选其一，符合分组背包类似于“每组物品中只能选一个”的性质。由此可知，本题可以设法使用分组背包来做。
根据四种互斥情况，我们规定每组物品：
第一个物品的价格和实际权重等于主件；
第二个物品的价格和实际权重等于主件+第一个附件；
第三个物品的价格和实际权重等于主件+第二个附件；
第四个物品的价格和实际权重等于主件+第一个附件+第二个附件；
又因为主件=第一个物品，主件+第一个附件=第二个物品，故上述规定可以表示为：
第一个物品的价格和实际权重等于主件；
第二个物品的价格和实际权重等于第一个物品+第一个附件；
第三个物品的价格和实际权重等于第一个物品+第二个附件；
第四个物品的价格和实际权重等于第二个物品+第二个附件；
#include <bits/stdc++.h>
using namespace std;
struct T
{
int w, t;
};
vector<T> V[65];
int n, m, a, b, c, dp[32005];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &a, &b, &c);
//提前记录当前主件和该主件已出现的附件的总数，避免后面出现死循环
int t = V[c].size();
if (!c)
{
//处理主件
V[i].push_back({a, a * b});
}
else
{
//处理附件
for (int k = 0; k < t; k++)
V[c].push_back({a + V[c][k].w, a * b + V[c][k].t});
}
}
for (int i = 1; i <= m; i++)
for (int j = n; j >= 0; j--)
for (int k = 0; k < V[i].size(); k++)
{
T now = V[i][k];
if (j >= now.w)
dp[j] = max(dp[j], dp[j - now.w] + now.t);
}
cout << dp[n];
return 0;
}
7.4827: 借教室
NOIP2012提高组Day2T2
枚举每一种订单，然后针对每一种订单，对区间内的每一天进行修改（做减法），直到某一份订单使得某一天剩下的教室数量为负数，即可得出结果。复杂度是m*n的
维护一个区间最小值来判断是否可以安排 每个叶子节点表示第几天的剩余教室 然后订就是区间减法，然后同时判断一下就可以了
会被卡内存，又一次被内存坑了
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000010;
struct segment{
int l,r,minn,minus;
}tree[maxn<<2];
int n,m,l,r,s;
void build(int l,int r,int now)
{
tree[now].l=l,tree[now].r=r;
if(l==r)
{
scanf("%d",&tree[now].minn);
return;
}
int mid=(l+r)>>1;
build(l,mid,now<<1);
build(mid+1,r,now<<1|1);
tree[now].minn=min(tree[now<<1].minn,tree[now<<1|1].minn);
}
void update(int now)
{
tree[now].minn=min(tree[now].minn,min(tree[now<<1].minn-tree[now<<1].minus,tree[now<<1|1].minn-tree[now<<1|1].minus));
}
void change(int l,int r,int now,int num)
{
if(tree[now].l==l&&tree[now].r==r)
{
tree[now].minus+=num;
return;
}
int mid=(tree[now].l+tree[now].r)>>1;
if(r<=mid) change(l,r,now<<1,num);
else if(l>mid) change(l,r,now<<1|1,num);
else change(l,mid,now<<1,num),change(mid+1,r,now<<1|1,num);
update(now);
}
int main()
{
scanf("%d%d",&n,&m);
build(1,n,1);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&s,&l,&r);
change(l,r,1,s);
if(tree[1].minn-tree[1].minus<0)
{
printf("-1
%d",i);
return 0;
}
}
printf("0");
}
当然也有人写差分数组