本文共 382 字，大约阅读时间需要 1 分钟。

【题目】

【题解】

将题目转化成选取一些物体，使得价值总和不小于h的所选物体的最小体积和这样一个完全背包问题，每个物体可以选择多次。

临界值为什么可以是2e4呢？因为我们考虑最坏的情况，就是当h=1e4时，选择很划算的价值x为999的物品*2。

临界值为什么不可以是h+h呢？因为考虑h很小而性价比最高的物体价值很大的情况，比如h=1,物品a的x=10000,y=1.

【代码】 

#include 
   
    using namespace std;const int N=2e4+10;const int INF=0x3f3f3f3f;int dp[N];int main(){    int h,n; scanf("%d%d",&h,&n);    memset(dp,INF,sizeof dp);    dp[0]=0;    for(int i=0;i
   

转载地址：http://uefen.baihongyu.com/