2020icpc沈阳H

优化转移DP

题意

Aloha 要骑单车，可以单独花费 \(r\) 元骑 1 次，也可以购买某一种单车卡，第 \(i\) 种单车卡 \(c_i\) 元，若在第 \(t\) 天购买，可以在 \([t,t+d_i-1]\) 天使用，并且最多使用 \(k_i\) 次

给出 Aloha 一段时间内的单车使用情况，求出他需要的最小花费

给出

\(n\;(1<=n<=500)\), 单车卡的种类
\(m\;(1<=m<=10^5)\), \(m\) 条使用记录
\(r\;(1<=r<=10^9)\), 单独骑 1 次的花费
\(n\) 行，每行有 \(1<=d_i,k_i,c_i<=10^9\), 第 \(i\) 种单车卡的有效期、使用次数、价格
\(m\) 行，每行有 \(0<=p_i<=10^9,\;0<=q_i<=3e5,\;\sum\limits_{i=1}^mq_i<=3e5\)

表示在第 \(p_i\) 天骑了 \(q_i\) 次

思路

看上去就是 DP，观察数据范围，很多数据的值域过大，只有 \(n\) 和 \(\sum q_i\) 可能与 DP 复杂度有关

求出每次骑的时间 \(a[i]\), 一共骑了 cnt 次，并按时间排序；

设 \(f[i]\) 为骑完前 \(i\) 次的最小花费，\(ptr[i][j]\) 为如果第 \(i\) 次可以用到第 \(j\) 个卡，则最早在第 \(ptr[i][j]\) 次骑完后买卡

可列出朴素DP转移

for (int i = 1; i <= cnt; i++)

{

    f[i] = f[i - 1] + r;//初始化为不买卡直接骑

    for (int j = 1; j <= n; j++)

    {

        auto [d, k, c] = b[j];

        for (int w = ptr[i][j]; w < i; w++)

            f[i] = min(f[i], f[w] + c);

	}

}

由于 \(f[i]\) 是单调不减的，因此 \(f[i]=min(f[i],f[w]+c)\) 中 \(w=ptr[i][j]\) 时是最优的（也可以感性地感受一下，这样卡的利用率更高，这样好像倒推更好理解一点，有时间试试）
接下来就是需要求出 \(ptr[i][j]\)，第一维可以优化掉，\(ptr[j]\) 表示第 i 次骑车时，最早需要 \(ptr[j]\)次后买第 j 种卡才能覆盖第 i 次

随着 \(i\) 增大，\(ptr[j]\) 不会回退，因此可以暴力 check，双指针维护

代码

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

typedef pair<int, int> PII;

const int N = 3e5 + 10;

int n, m;

ll r;

struct Cards

{

	ll d, k, c;

}b[510];

int a[N];//第i次的时间

int cnt;

ll f[N];//前i次的最小代价

int ptr[510];

bool check(int now, int card)

{

	int last = ptr[card];

	auto [d, k, c] = b[card];

	if (last == now)

		return true;

	if (a[last] + d - 1 < a[now])

		return false;

	if (now - last + 1 > k)

		return false;

	return true;

}

int main()

{

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m >> r;

	for (int i = 1; i <= n; i++)

		cin >> b[i].d >> b[i].k >> b[i].c;

	for (int i = 1; i <= m; i++)

	{

		int p, q;

		cin >> p >> q;

		while(q--)

			a[++cnt] = p;

	}

	sort(a + 1, a + cnt + 1);

	for (int i = 1; i <= n; i++)

		ptr[i] = 1;

	for (int i = 1; i <= cnt; i++)

	{

		f[i] = f[i-1] + r;

		for (int j = 1; j <= n; j++)

		{

			auto [d, k, c] = b[j];

			// for (int w = ptr; w < i; w++)

			// 	f[i] = min(f[i], f[w] + c);

			// 因为f[i]单调递增，因此取w=x最小，ptr为在第ptr次后买优惠券，正好可以覆盖到第i次，双指针更新ptr

			while(!check(i, j))

				ptr[j]++;

			f[i] = min(f[i], f[ptr[j] - 1] + c);

			// cout << i << ": " << j << " " << ptr[j] << endl;

		}

	}

	cout << f[cnt] << endl;

    return 0;

}

巴特西

2020icpc沈阳H

优化转移DP

题意

思路

代码

最新文章

热门文章