题意描述

数轴上分布着 $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

6

数据范围与约定

对于 $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$ 时的最大收益,则有

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


100pts

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

考虑从右往左 dp ,设 $f[i][j]$ 表示走到第 $i$ 个礼品店后掉头,收益为 $j (j < \frac{e}{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;
}

THE END