牛客题霸--牛能和牛可乐的礼物 题解

牛能和牛可乐的礼物

C++版本答案：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
const int MAXN=200020;
const int MID=100010;
class Solution {
public:
  bool vis[2][MAXN];
  queue<int> Q[2];
  int maxPresent(vector<int>& presentVec) {
      int n=presentVec.size();
      memset(vis,0,sizeof(vis))
      int cur=0;Q[cur].push(MID);
      vis[cur][MID]=1;
      for(int i=0;i<n;++i) {
    const int val=presentVec[i];int nxt=cur^1;
    while(!Q[nxt].empty()) Q[nxt].pop();
    while(!Q[cur].empty()) {
      int S=Q[cur].front();
      vis[cur][S]=0;
      if(!vis[nxt][S-val]) vis[nxt][S-val]=1,Q[nxt].push(S-val);
      if(!vis[nxt][S+val]) vis[nxt][S+val]=1,Q[nxt].push(S+val);
      Q[cur].pop();
    }
    cur^=1;
      }
      int ans=1e9;
      for(int i=0;i<MAXN;++i) if(vis[cur][i]) ans=min(ans,abs(i-MID));
      return ans;
  }
}S;
vector<int> pr;
int main()
{
  int n;cin>>n;pr.resize(n);
  for(int i=0;i<n;++i) scanf("%d",&pr[i]);
  printf("%d\n",S.maxPresent(pr));
}

一道简单的动态规划题。
设 表示当前到了第 i 件礼物,两组礼物价值和差值为 j 是否可行,将所有j均加上一个偏移量即可避免负数下标的情况。

假设当前的礼物价值为 , 那么对于 为 时转移
数组第一维可以滚掉，中间枚举为真的 时可以用队列实现。
最后扫描一遍数组得到最小的答案即可。