Day3-T2

原题目

　　奶牛Bessie的电脑总是无缘无故地被 FJ 关掉，奶牛 Bessie 非常苦恼，也非常生气。FJ 却发现了一个很神奇的规律（别问是怎么知道的），发现 Bessie 每吃一次草，她的生气值会减少一个特定的值。 FJ也知道生气的奶牛是不利于产奶的，于是 FJ 开始精心饲养奶牛 Bessie，使她的生气值降低，防止发生不必要的冲突，然后再来关 Bessie 的电脑。

　　第 1 行，n,m,k。n 表示 FJ 给 Bessie 吃草的次数，m 表示 Bessie 的饭量，k 为 Bessie 初始生气值。第 2 到第 n+1 行，第 i+1 行两个数 ai 和 bi；ai:吃完第 i 次草 Bessie 的饱涨度，bi:吃完第 i 次草 Bessie 的生气值就减去 bi。

　　输出共一行一个整数，Bessie 最小的生气值（非常可能为负，因为 Bessie 是个活泼开朗的牛儿）.

　　Input：

　　Output：

　　Describe：背包模板题.....However，Juruo还是误解了 [ 第 i 次 ] 的意思，打成了模拟...

　　code：

#pragma GCC optimize(2)

#include<bits/stdc++.h>

#define rep1(a,b) for(register int i=(a);i<=(b);i++)

#define rep2(a,b) for(register int j=(a);j<=(b);j++)

using namespace std;

long long f[5005],n,m,k,ans;

long long a[5010],b[5010];

inline int read(){

    int ret=0,f=1;char ch=getchar();

    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}

    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();

    return ret*f;

}

inline double read2(){

    double X=0,Y=1.0;int w=0;char ch=0;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=X*10+(ch^48),ch=getchar();

    ch=getchar();

    while(isdigit(ch)) X+=(Y/=10)*(ch^48),ch=getchar();

    return w?-X:X;

}

inline void write(int x){

    if(x<0){putchar('-');write(-x);return;}

    if(x/10) write(x/10);

    putchar(x%10+'0');

}

int main(){

    //freopen("anger.in","r",stdin);

    //freopen("anger.out","w",stdout);

    n=read(),m=read(),k=read();

    for(register int i=1;i<=n;i++)cin>>a[i]>>b[i];                       //m:容量，a[i]:体积，b[i]:价值

    for(register int i=1;i<=n;i++){

        for(register int j=m;j>=a[i];j--){

            f[j]=max(f[j],f[j-a[i]]+b[i]);

        }

    }

    cout<<k-f[m];

//    int i=1;

//    while(m>=0&&i<=n){

//        m-=a[i];

//        ans+=b[i];

//        if(m<0)ans-=b[i];

//        i++;

//    }

//    cout<<k-ans;

    return 0;

}

/*

3 3 8

1 2

2 3

8 1000

*/

巴特西

Day3-T2

最新文章

热门文章