首页 > 其他分享 >2020icpc沈阳H

2020icpc沈阳H

时间:2022-10-26 15:22:19浏览次数:81  
标签:cnt return int 沈阳 2020icpc last now ptr

优化转移DP

Problem - H - Codeforces

题意

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

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

给出

  1. \(n\;(1<=n<=500)\), 单车卡的种类

  2. \(m\;(1<=m<=10^5)\), \(m\) 条使用记录

  3. \(r\;(1<=r<=10^9)\), 单独骑 1 次的花费

  4. \(n\) 行,每行有 \(1<=d_i,k_i,c_i<=10^9\), 第 \(i\) 种单车卡的有效期、使用次数、价格

  5. \(m\) 行,每行有 \(0<=p_i<=10^9,\;0<=q_i<=3e5,\;\sum\limits_{i=1}^mq_i<=3e5\)

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

思路

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

  2. 求出每次骑的时间 \(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);
    	}
    }
    
  3. 由于 \(f[i]\) 是单调不减的,因此 \(f[i]=min(f[i],f[w]+c)\) 中 \(w=ptr[i][j]\) 时是最优的(也可以感性地感受一下,这样卡的利用率更高,这样好像倒推更好理解一点,有时间试试)

  4. 接下来就是需要求出 \(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;
}

标签:cnt,return,int,沈阳,2020icpc,last,now,ptr
From: https://www.cnblogs.com/hzy717zsy/p/16828508.html

相关文章

  • 2021ICPC沈阳站 J Luggage Lock 思路以及C++实现
    题目JLuggageLock思路我们可以将密码锁的每一个状态看成一个节点,每一个操作看成从一个节点到另一个节点的权重为1(意思是经过一次操作)的有向边,这个问题就可以看成一个......
  • 爱数课平台支持沈阳航空航天大学线上直播教学
    01应用背景2020年2月25日沈阳航空航天大学获批大数据管理与应用专业。本专业培养适应我国社会主义经济发展和现代化建设需要,德、智、体、美、劳全面发展,具备系统的计算机、......
  • 2020icpc济南 - A
    组合数学+高斯消元[A-MatrixEquation_第45届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南)(nowcoder.com)](https://codeforces.com/problemset/problem/1632/D)题意......
  • 2021 ICPC 沈阳
    队里状态不是很好,就打了两个小时,算是复健场。赛时两题,补题补到四题。E-EdwardGaming,theChampion小评\(\mathcal{Consider\by\\pmb{Wida}}\),\(\mathcal{Sol......
  • 第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛(沈阳)
    有时候,很简单的模板题,可能有人没有做出来,(特指I),到时候一定要把所有的题目全部看一遍目录B题解EF题解HI题解&代码JB输入样例32121231输出样例1说明In......
  • 2020ICPC上海I - Sky Garden
    思维[I-SkyGarden_第45届国际大学生程序设计竞赛(ICPC)亚洲区域赛(上海)(重现赛)@hzy0227(nowcoder.com)](https://codeforces.com/gym/103202/problem/I)题意有\(n\;(1<......
  • 2020ICPC沈阳I - Rise of Shadows
    剩余系Problem-I-Codeforces题意给定\(H,M,A\)\(2<=H,M<=10^9,\;0<=A<=\frac{H*M}2\)假设一个钟表有\(H\)小时,一小时有\(M\)分钟,求一天中有多少整数分钟,满......