专栏文章

题解：P14306 【MX-J27-T3】旋律

QQWQAWAQWQAWA
P14306题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minia98b
此快照首次捕获于
2025/12/02 02:52
3 个月前
此快照最后确认于
2025/12/02 02:52
3 个月前
查看原文

P14305

解法说明

分析

同一个机房的很多人想复杂了。此题和数之间的差有关，选择数值接近的数更好，故一开始可以先排序。分析样例，我认为可以通过动态规划解决。

思路

首先进行排序。之后，对于每一个数，dp[i]dp[i] 表示最后一个数为第 ii 小的数时，所取到的最大值。为了取到最大，每一个数要不然只选自己一个，要不然也选上一个数。状态转移方程为 dp[i]=max⁡(k,dp[i−1]+k−(a[i]−a[i−1]))dp[i]=\max(k,dp[i-1]+k-(a[i]-a[i-1]))。尽管赛场上我没有严格证明，但觉得这个做法是对的，这个时候犹豫可能反而会败北。
当然，可以进一步优化空间复杂度，利用两个变量代替数组，这个方法叫滚动数组，此处代码是优化前的。

代码

CPP
#include <bits/stdc++.h>
using namespace std;
long long c,T,n,k,a[100005],dp[100005],ans;
int main()
{
	cin>>c>>T;
	while(T--){
		cin>>n>>k;ans=0;
		
		for(int i=1;i<=n;i++){
			cin>>a[i];dp[i]=0;
		}
		sort(a+1,a+n+1);
		dp[1]=k;ans=k;
		for(int i=2;i<=n;i++){
			dp[i]=k;
			dp[i]=max(dp[i],dp[i-1]+k-(a[i]-a[i-1]));
			ans=max(ans,dp[i]);
		}
		cout<<ans<<endl;
	}

	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...