题意描述

数轴上分布着 $n$ 个礼品店，第 $i$ 个礼品店在位置 $i$。进入礼品店 $i$ 后，你能够购买一个重量为 $a_i$ 的礼品，每个物品最多购买一次。

你需要从 $0$ 位置出发，最后返回 $0$位置。每次可以选择购买当前位置的礼品，或者向左或右移动 $1$ 单位的距离。

如果你当前携带着重量之和为 $s$ 的礼品，每次移动你需要消耗 $s+1$ 的能量。

问在消耗不超过 $e$ 的能量的情况下，最多能带回多少重量的礼品。

输入格式

第一行包含两个整数 $n,e$，表示礼品店的数量和消耗能量的上界。

第二行包含 $n$ 个整数 $a_i$ ，表示第 $i$ 个礼品店中礼品的重量。

输出格式

共一行一个整数，表示最多能带回的礼品的重量。

Input & Output ‘s examples

Input ‘s eg

4 25
3 30 1 3

Output ‘s eg

数据范围与约定

对于 $20\%$ 的数据，满足 $n \le 20,e \le 10^2$。

对于 $40\%$ 的数据，满足 $n \le 10^3, e \le 3 \cdot 10^3$。

对于 $70\%$ 的数据，满足 $n \le 10^5, e \le 3\cdot 10^5$。

另有 $10\%$ 的数据，满足 $a_i \le 1$。

对于全部数据，满足 $1 \le n \le 10^6, 1 \le e \le 3 \cdot 10^7, 0 \le a_i \le 10^6$。

分析

~~考场上硬是没看出来背包~~

40pts

物品只要在身上就会在移动时花费相应的体力，我们要尽量节省体力，故要让每个物品在身上的时间尽量的短。

故最优策略一定是走到某个物品 $x$ 之后掉头往左走，在回来的路上购买其他物品。

设 $f[i][j]$ 表示走到第 $i$ 个物品后掉头，花费体力为 $j$ 时的最大收益，则有

$f[i][j] = max(f[i - 1][j] , f[i - 1][j - i \times a[i]] + a[i])$

时间复杂度 $O(n \times e)$ ，无法通过本题，但可以拿到 $40$ 分的好成绩。

100pts

满分做法需要发现一个小性质：对于一个物品 $i$ ，若 $e < a[i] \times i$，则该物品一定无法选择。

考虑从右往左 dp ，设 $f[i][j]$ 表示走到第 $i$ 个礼品店后掉头，收益为 $j (j < \frac{e}{i})$ 所需要的最小体力。则有转移：

$f[i][j] = max(f[i - 1][j] , f[i - 1][j - a[i]] + i \times a[i])$

状态总数为 $\sum_{i = 1}^{n} \frac{e}{i}$，故时间复杂度为 $O(e \log n)$，足以通过所有数据。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#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 PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 30000000 + 5;
const int HA = 998244353;

int n , e , a[M];

ll f[M] , ans;

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    read(n) , read(e);
    rep(i , 1 , n) read(a[i]);
    
    clean(f , 0x3f3f3f3f);
    per(i , n , 1) {
        if(a[i] * i > e) continue;
        
        int lim = e / i;
        f[0] = 2 * i;
        per(j , lim , a[i]) f[j] = min(f[j] , f[j - a[i]] + a[i] * i);
    }
    per(i , e , 0) {
        if(f[i] <= e) {
            return printf("%d\n" , i) , 0;
        }
    }

    return 0;
}