CodeForces - 35D

题目：https://vjudge.net/contest/326867#problem/A

题意：有一个农场，自己有m斤粮食，有n天，每天动物吃的量不同，那个动物的食量的是由他是从那天开始进这个农场确定的，后面不能再变，从这天进来后就必须吃到第n天，每天只能进来一个动物，问最后能被保留下来的动物数最大是多少

思路：

1.贪心+排序，既然他每天只能进入一个动物，而且动物进来后食量不变，而且进来知道吃多少天，那么相当于我们知道所有动物的消费粮食值是多少个，然后我们直接排序，选取最少的那几个即可 O（nlogn）

#include<bits/stdc++.h>

#define maxn  100005

#define mod 1000000007

using namespace std;

typedef long long ll;

ll a[maxn],n,m;

int main(){

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

    cin>>n>>m;

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

        cin>>a[i];

        a[i]=a[i]*(n-i+);

    }

    sort(a+,a+n+);

    int num=;

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

        if(m>=a[i]){

            m-=a[i];

            num++;

        }

        else break;

    }

    printf("%d",num);

}

2.DP ,一样和上面，我们可以知道每个动物的消费粮食值，我们可以转化为一个01背包问题， O(n*m),主要还是当dp题来练手

#include<bits/stdc++.h>

#define maxn  100005

#define mod 1000000007

using namespace std;

typedef long long ll;

ll a[maxn],n,m;

ll dp[maxn];

int main(){

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

    cin>>n>>m;

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

        cin>>a[i];

        a[i]=a[i]*(n-i+);

    }

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

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

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

        }

    }

    printf("%d",dp[m]);

}