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=1;i<=n;i++){
        cin>>a[i];
        a[i]=a[i]*(n-i+1);
    }
    sort(a+1,a+n+1);
    int num=0;
    for(int i=1;i<=n;i++){
        if(m>=a[i]){
            m-=a[i];
            num++;
        }
        else break;
    }
    printf("%d",num);
}

View Code

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=1;i<=n;i++){
        cin>>a[i];
        a[i]=a[i]*(n-i+1);
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i];j--){
            dp[j]=max(dp[j],dp[j-a[i]]+1);
        }
    }
    printf("%d",dp[m]);
}

View Code