题解 P2918 【[USACO08NOV]买干草Buying Hay】

田阙西 · 2018-08-16 19:51:29 · 题解

我和各位脑回路似乎不太一样。。。。

仍然以钱为体积找max，但是要找到第一个符合条件的i的话，我们并不能证明至少要多少钱。

代码中的minn只是个估计量，+500，5000都过不去，要加到50000才行。这是完全没有道理的，真的。。。。

所以不太建议大家像我这样写。。。

尽量还是用稳妥一点的方法吧，比如像楼上几位那样

错误示例（雾）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
int n,h,minn;
int v[110],w[110],f[1000000];
int fastRead()
{
    int f=1,re=0;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){re=re*10+ch-'0';ch=getchar();}
    return f*re;
}
int main()
{
    n=fastRead(),h=fastRead();
    for(int i=1;i<=n;i++)
    {
        v[i]=fastRead(),w[i]=fastRead();
        minn=min(minn,w[i]*h/v[i]);
    }
    for(int i=1;i<=n;i++)
    for(int j=w[i];j<=minn*h+50000;j++)
    f[j]=max(f[j],f[j-w[i]]+v[i]);
    for(int i=1;i<=minn*h+50000;i++)
    if(f[i]>=h){printf("%d\n",i);break;}
    return 0;
}