Submission #58795785

---

Source Code Expand

// LUOGU_RID: 182045020
// ABC374F - Shipping
#include<bits/stdc++.h>

using namespace std;

typedef long long i64;

constexpr i64 INF = 0x3f3f'3f3f'3f3f'3f3f;
int n, m, tot;
i64 x;
vector<i64> t, d, mn;
vector<vector<i64>> f;
// f(i, j): 前i件货物，最后一件在第d[j]天发货时，最小的不满意度 

int main()
{
	cin >> n >> m >> x;
	t.resize(n + 1);
	d.push_back(0);
	for(int i = 1; i <= n; i++)
	{
		cin >> t[i];
		for(int j = 0; j <= n; j++)
			d.push_back(t[i] + j * x); // d: 可能发货的日期的集合 
	}
	sort(d.begin(), d.end());
	d.erase(unique(d.begin(), d.end()), d.end());
	tot = (int)d.size() - 1; // tot = O(n^2)
	
	f.resize(n + 1, vector<i64>(tot + 1, INF));
	f[0][0] = 0;
	for(int i = 1; i <= n; i++)
	{
		int lst = 0;
		for(int j = 1; j <= tot; j++)
		{
			if(d[j] < t[i]) continue;
			while(lst < tot && d[lst + 1] <= d[j] - x) lst++;
			for(int k = 1; k <= min(i, m); k++) // 枚举一次发货的货物数量
				f[i][j] = min(f[i][j], f[i - k][lst] + k * d[j]);
			f[i][j] = min(f[i][j], f[i][j - 1]);
		}
	}
	
	i64 ans = *min_element(f[n].begin() + 1, f[n].end())
	        - accumulate(t.begin(), t.end(), 0ll);
	cout << ans << endl;
	
	return 0;
}

Submission Info

Judge Result