WZK的减肥计划

来源和评测点

NOIP2009 赛前集训(CZYZ2009 暑假集训提高组 5)

题目

【题目大意】
有 n 种食品可供 WZK 选择,每种物品都有给定的价格,卡路里和拥有数量,
选出一些食品使得总卡路里大于要求量且最小,
如果有多种组合满足条件, 则取价格最小的。
【输入格式】
第一行为两个整数 n(0<n<=100),k(0<k<=10^5)
分别表示物品个数和一天消耗的最少卡路里。
接下来n行每行 3 个整数,costi,mi,cali
(0< costi,1<=mi<=100,cali<10^6)
分别表示价格,数量和所含卡路里。
输入数据保证合法、有解。
【输出格式】
满足条件的总卡路里和总价格,中间用一个空格隔开。
注意:保证答案的总卡路里小于 10^5,总价格小于 10^8。
【输入样例】
5 10
10 2 6
5 1 9
6 1 6
9 1 6
5 1 9
【输出样例】
12 15

分析

话说今天生日耶,刷个卡~

注意,逻辑上答案应该是可以何要求值(原题为WZK的需求量)一样的,
但题目确实要求大于,机房许多大佬都错了,就是因为这个,暴0
时间复杂度nk,应该这个才是正解,虽然数据水体现不出来
注意现在更像多重背包了
重点:c也就是使用量只跟物品有关,考试时以为实现不出来

代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int mymin(int a,int b) {return a<b?a:b;}
int f[100010],c[100010];
int main()
{
freopen("plan.in","r",stdin);
freopen("plan.out","w",stdout);
memset(f,63,sizeof(f));
f[0]=0;int mi=100000;
int n,k;scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)//100
{
memset(c,0,sizeof(c));//c=在这个物品下,f对应的物品使用量
int cost,m,cal;scanf("%d%d%d",&cost,&m,&cal);
for(int j=0;j<=k;j++)//100000
{
if(c[j]<m)
{
int ca=j+cal;
if(ca>k and ca<mi) mi=ca;
if(f[j]+cost<f[ca])
{
c[ca]=c[j]+1;
f[ca]=f[j]+cost;
}
}
}
}
printf("%d %d\n",mi,f[mi]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/f8f3.html
转载请注明出处,谢谢!