题解：P3957 [NOIP2017 普及组] 跳房子

JayJessy · 2024-07-02 16:41:54 · 题解

难道有人看题解不点赞的吗？

题目解析

这道题可以使用二分+动态规划，二分要花的金币数。

50pts：

简单的 ok 函数：

bool ok(ll g) {
    memset(dp,-0x3f,sizeof(dp));
    dp[0]=0;
    ll ans=0;
    for(ll i=1; i<=n; i++) {
        for(ll j=i-1; j>=0; j--) {
            if(x[i]-x[j]>d+g) break;
            if(x[i]-x[j]>=max(1ll,d-g)) dp[i]=max(dp[i],dp[j]+s[i]);
        }
        ans=max(ans,dp[i]);
    }
    return ans>=k;
}

然后就发现程序超时，只有 50 分。

100pts：

很明显需要优化 ok 函数。
可以发现对于 dp_i 需要维护 [i-mn,i+mx] 的最大值。
欸，这不就是单调队列吗？
对于 dp_i：

• 先将所有满足 j\lt i 且 x_i-x_j \ge mn 的 j 加进队尾。

  while(j<i && x[i]-x[j]>=mn) {
  if(dp[j]>-1e18) {
      while(!q.empty() && dp[q.back()]<=dp[j]) q.pop_back();
      q.push_back(j);
  }
  j++;
  }

• 接下来将队头 x_i-x_{q.front()} \gt mx 的元素删去。

  while(!q.empty() && x[i]-x[q.front()]>mx) q.pop_front();

• 最后将 dp_i 赋值为 x_{q.front()}+s_i 并算出答案。

  if(!q.empty()) dp[i]=dp[q.front()]+s[i];
  ans=max(ans,dp[i]);

  呼，该说的都说完了，接下来就是……

  AC 代码

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  const ll N=5e5+10;
  deque<ll> q;
  ll n,d,k,l,r=1e9,x[N],s[N],dp[N];
  bool ok(ll g) {
  q=deque<ll>();
  memset(dp,-0x3f,sizeof(dp));
  dp[0]=0;
  ll mn=max(1ll,d-g),mx=d+g,j=0,ans=0;
  for(ll i=1; i<=n; i++) {
      while(j<i && x[i]-x[j]>=mn) {
          if(dp[j]>-1e18) {
              while(!q.empty() && dp[q.back()]<=dp[j]) q.pop_back();
              q.push_back(j);
          }
          j++;
      }
      while(!q.empty() && x[i]-x[q.front()]>mx) q.pop_front();
      if(!q.empty()) dp[i]=dp[q.front()]+s[i];
      ans=max(ans,dp[i]);
  }
  return ans>=k;
  }
  int main() {
  freopen("jump.in","r",stdin);
  freopen("jump.out","w",stdout);
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>d>>k;
  for(ll i=1; i<=n; i++) cin>>x[i]>>s[i];
  while(l<r) {
      ll mid=(l+r)>>1;
      if(ok(mid)) r=mid;
      else l=mid+1;
  }
  if(l>=1e9) cout<<-1;
  else cout<<l;
  return 0;
  }

  完结撒花~~