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

· · 题解

P14305

解法说明

分析

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

思路

首先进行排序。之后，对于每一个数，dp[i] 表示最后一个数为第 i 小的数时，所取到的最大值。为了取到最大，每一个数要不然只选自己一个，要不然也选上一个数。状态转移方程为 dp[i]=\max(k,dp[i-1]+k-(a[i]-a[i-1])) 。尽管赛场上我没有严格证明，但觉得这个做法是对的，这个时候犹豫可能反而会败北。

当然，可以进一步优化空间复杂度，利用两个变量代替数组，这个方法叫滚动数组，此处代码是优化前的。

代码

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