https://codeforces.com/contest/1132/problem/E

大意比较简单，说一下吧：

8个物品，权依次为1~8,第i个物品有cnt[i]([0,1e16])个

给定一个n([1,1e18]),

从物品中取出若干个，可使得取出物品的总权值为sum,求在sum<=n的条件下，sum的最大值

 

题解用的技巧很巧妙，取1~8的LCM为L

那么sum可以化为AL+B

对于物品i,可以分为2部分，

一部分从中取出 qi个(qi<=L/i)，那么这部分的总权值小于L

另一部分按照 L/i  个为1捆，分成若干(pi)/捆，我们从中取出的捆数就是[0,pi]

当q[i]从0到L/i-1遍历时，对于物品i就经历了所有的情况

 

具体的:

我们为每个i确定一个q[i],那么对于某一种情况，我们记录下它的所有物品的p[i]的和，那么

这种情况就可以得到sumq[i]+L*[0,sump[i]]的权值和，这种情况就可以很方便的计算sum最大值了

当然了，不能暴力所有情况，要加一层DP,用dp[i][j]记录使用前n个物品sumq[i]时的sump[i]

,这样复杂度就是 8*(L*8)*,最大就4e7左右吧，其实复杂度有点险，但还是能过

 

最后贴个代码

#define CLR(a) memset((a),0,sizeof(a))
#define RE(i,a) for(int i=0;i<(int)a;++i)
#define RE2(i,a) for(int i=1;i<=(int)a;++i)
#define F2(i,a,b) for(int i=a;i>=b;--i)
#define F(i,a,b) for(int i=a;i<=b;++i)
#define PB push_back
#define PII pair<int,int>
#define x first
#define y second
/////////////////////////////////////////////////
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int maxn = int(9);
const int L = 840;
ll n;
ll cnt[9];
ll dp[maxn][9 * L];
int main()
{
	//	freopen("C:\\Users\\VULCAN\\Desktop\\data.in","r",stdin);
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T(1), cas(0);
	while (++cas, T--)
	{
		cin >> n; RE2(i, 8)cin >> cnt[i];
		memset(dp, -1, sizeof(dp));
		dp[0][0] = 0;
		RE2(i, 8)
		{
			RE(j, 8 * L+1)
			{
				int up = min(1ll * L / i, cnt[i]);
				F(k,0,up)
				{
					if (j - i * k < 0)break;//非法
					if (dp[i - 1][j - i * k] == -1)continue;
					ll &ret = dp[i][j];
					ret = max(ret, dp[i - 1][j - i * k] + (cnt[i] - k) / (L / i));
				}
			}
		}
		ll ans(0);
		RE2(j, 8 * L)if (j <= n && ~dp[8][j])
		{
			ll res = n - j;
			ll fil = min(dp[8][j] * L, res / L * L);
			ans = max(ans, fil + j);
		}
		cout << ans << endl;
	}
	return 0;
}