2022河南萌新联赛第（七）场：南阳理工学院 D 疯狂星期八

原题链接

去掉题目限制，题目是一个普通的01背包问题，我们可以用dp[i][j]表示当选择到第i个食物时此时加上第i个食物已经吃了多少个食物，答案为 j 从大到小枚举，当dp[x][j]<=m时为答案j，但没有题目限制j会非常大时间复杂度为O(nm)

加上题目限制后，m的最大值为1e5，假如我们取100个食物，从1到100，我们会发现即时是最小的100个加起来也会超过1e5所以，我们取的食物不可能大于100，这样就把 j 控制在100,O(100n)显然可以过掉，枚举每个食物时要从后往前枚举，因为无论选择哪些物品，从后往前取食物比任何取法都花费少

证明:

某两个食物i在前j在后 i × x+j×(x+n)与i×(x+n)+j×x

后者减掉前者得到 (i-j)×n<0,所以在选定食物的情况下，后面的食物先选一定比后选花费少

code:

// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")

#include <iostream>
#include <cstring>
#include <algorithm>
#include<string>
#include <vector>
#include<set>
#include<queue>
#include<map>
#include<cmath>
#include<deque>
#include<climits>
#include<bitset>
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int>PII;
typedef pair<int,char>PIC;
typedef pair<int,pair<int,int> > PPI;
#define mest(x,y) memset(x,y,sizeof x)
#define endl "\n"
#define all(x) x.begin(), x.end()
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fi first 
#define se second 
#define ppb pop_back
#define pb push_back
#define rep(i, l, r) for(int i = l; i <= (r); ++ i)
#define per(i, r, l) for(int i = r; i >= (l); -- i)
#define reps(i, l, r, d) for(int i = l; i <= (r); i += d)
#define pers(i, r, l, d) for(int i = r; i >= (l); i -= d)
const int N = 1e5+10,M=N*2;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f3f3f3f3f;
int h[N],ne[M],e[M],idx;
int dp[N][110];
int a[N];
void solve()
{
    mest(dp,0x3f);
    int n,m;cin>>n>>m;
    rep(i,1,n)cin>>a[i];
    dp[n+1][0] = 0;
    per(i,n,1)
    {
      rep(j,0,100)
      {
        dp[i][j] = dp[i+1][j];
        if(j)dp[i][j] = min(dp[i+1][j-1]+a[i]+i*(j-1),dp[i][j]);
      }
    }
    int ans = 0;
    per(i,100,1)
    {
      if(dp[1][i]<=m)
      {
        ans = i;
        break;
      }
    }
    cout << ans <<endl;
    return ;
}
signed main()
{
    IOS;
    int t = 1;
    while(t--)
    {
      solve();
    }
    
	  return 0;
}