题目：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); }
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]); }
原文：https://www.cnblogs.com/Lis-/p/11541728.html
