首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

洛谷 P1687 机器人小Q(DP)

  • 25-02-16 18:40
  • 2537
  • 9955
blog.csdn.net

题目链接

https://www.luogu.com.cn/problem/P1687

思路

因为要按照顺序来给机器人充电,所以考虑 d p dp dp。

令 d p [ i ] [ j ] = { x , y } dp[i][j] = \{x,y\} dp[i][j]={x,y}表示从前 i i i个单位能量中选了 j j j个对机器人进行充电,所用的最小天数为 x x x,天数 x x x最小时最后一天的充电时长最短为 y y y。

状态转移方程为: d p [ i ] [ j ] = a d j ( d p [ i − 1 ] [ j ] , a d j ( d p [ i − 1 ] [ j − 1 ] , v [ i − 1 ] ) ) dp[i][j] = adj(dp[i - 1][j], adj(dp[i - 1][j - 1], v[i - 1])) dp[i][j]=adj(dp[i−1][j],adj(dp[i−1][j−1],v[i−1]))。其中, a d j ( ) adj() adj()函数起到取最小值的作用。

时间复杂度: O ( n k ) O(nk) O(nk)。

代码

#include 

using namespace std;

#define int long long
#define double long double

typedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;

const int N = 3e3 + 5, M = 5e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;

std::mt19937 rnd(time(0));

int n, k;
int a[N];
pii dp[2][N];
pii adj(pii a, pii b)
{
	if (a.first > b.first)
		return b;
	if (a.first < b.first)
		return a;
	if (a.second > b.second)
		a = b;
	return a;
}
pii adj(pii a, int b)
{
	if (a.second + b <= 119)
		a.second += b;
	else
	{
		a.first++;
		a.second = b;
	}
	return a;
}
int adj(int a, pii b)
{
	int res = b.first;
	if (b.second) res++;
	return max(a, res);
}
void solve()
{
	cin >> n >> k;
	vector<int>v;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (a[i] < 120) v.push_back(a[i]);
	}
	if (v.size() < k)
	{
		cout << "You can't do it." << endl;
		return;
	}
	int m = v.size();
	for (int i = 0; i <= m; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			dp[i & 1][j] = {inf, inf};
		}
	}
	dp[0][0] = {0, 0};
	for (int i = 1; i <= m; i++)
	{
		int idx = i & 1;
		for (int j = 1; j <= k; j++)
		{
			if (j > i) break;
			dp[idx][j] = adj(dp[idx ^ 1][j], adj(dp[idx ^ 1][j - 1], v[i - 1]));
		}
	}
	int ans = 0;
	ans = adj(ans, dp[m & 1][k]);
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
	// cin >> test;
	for (int i = 1; i <= test; i++)
	{
		solve();
	}
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
注:本文转载自blog.csdn.net的Auto114514的文章"https://blog.csdn.net/weixin_74754298/article/details/145348361"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

117
前沿技术
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top