洛谷 P1687 机器人小Q（DP）

题目链接

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

思路

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

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

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

时间复杂度：$O(nk)$。

代码

#include <bits/stdc++.h>

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;
}