dp practice_day 3

2023/3/7 Algorithm dp dp_practice_plan

做了一道状压，两道区间

CF 1012C

题意：给你n座山，你可以在山上修房子，但是该山的高度必须是比两侧的山要高，你可以花1来降低任何一座山的高度，询问建造[1,(n+1)/2]座房子所需的最小花费

题解：

 一开始不会做，看了题解之后明白了
 首先我们可以去贪心的想，对于两座相邻的山来说，我们只有可能去修改其中一座，因为修改两座和一座相同，然后这个问题我们可以集中在第i座山上来看。对于DP问题，<font color=red>最重要的就是找状态</font>
 那么在这里，有哪些状态呢？
 首先想，对于某一座山，我们可以选择修房子或者不修房子，这是状态1

 然后，我们遍历到了某座山的时候,我们需要记录一下，当前已经建造了多少间房子了，这是状态2

 最后，我们需要记录当前遍历的山的号码，这是状态3

 当我们得到状态之后，我们就考虑转移的问题,我们用dp[i][j][0/1]表示当前遍历到第i座山，已经建造了j间房子，当前这座山准备/不准备建造房子的最小花费

 首先考虑当前山不需要修建房子即，dp[i][j][0]
 很显然dp[i][j][0]只和a[i-1]和a[i]的大小有关系

 dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]+min(a[i]-a[i-1])+1)

 之后我们考虑当前山需要修建房子,由于不可能有连续的两座山需要修建房子，所以考虑第i-2座山，如果第i-2座山不需要修建房子，那么当前只需要考虑a[i]和a[i-1]的关系，即减去i-1比i高的部分即可

 否则我们需要考虑第i-2座山的高度，我们的i-1座山需要减去i-2和i之间的最小值的高度差,即

 dp[i][j][1]=min(dp[i-2][j-1][0]+max(0,a[i-1]-a[i]+1),dp[i-2][j-1][1]+max(0,a[i-1]-min(a[i],a[i-2])+1));

void solve()
{
  int n;cin>>n;
  vector<int>a(n+1);
  for(int i=1;i<=n;++i)cin>>a[i];
  int k=(n+1)/2;
  a[0]=INF;
  vector dp(n+1,vector<vector<int>>(k+1,vector<int>(2,INF)));
  dp[0][0][0]=dp[1][0][0]=dp[1][1][1]=0;//only transfer from these 3 situation
  for(int i=2;i<=n;++i)
  {
    dp[i][0][0]=dp[i-1][0][0];
    for(int j=1;j<=(i+1)/2;++j)
    {
        dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]+max(0,a[i]-a[i-1]+1));
        dp[i][j][1]=min(dp[i-2][j-1][0]+max(0,a[i-1]-a[i]+1),dp[i-2][j-1][1]+max(0,a[i-1]-min(a[i],a[i-2])+1));
    }
  }
  for(int i=1;i<=(n+1)/2;++i)
  {
    cout<<min(dp[n][i][0],dp[n][i][1])<<' ';
  }
  return;
}

CF 895C
题意：

 给你n个1到70之间的数，问你有多少种不同的方式能够让他们的乘机变成完全平方数

介绍状压和线性🐔的两种做法

1.状压:
首先我们需要知道，对于一个数，如果其为完全平方数，那么其对应的每一个质因子应该有偶数个

在这个基础上，我们看题目的范围，70，那么想到状压，由于小于70的质数只有19个，那么我们用二进制的每一位来表示某个数对应的质因数数量的奇偶

ok，预处理完了，下面继续找状态

状态1:当前处理的二进制状态j
状态2:当前处理的数的序号i

然后找转移，怎么转移呢？
我们知道，如果我们对原有状态，添加偶数个数，那么对应的状态不会发生改变（异或了之后都是0），添加奇数个数，直接在原有状态上异或对应的数的状态
那么转移也很好写了

dp[i][j]=(dp[i-1][j]+dp[i-1][j^st[i]])%MOD*p[a[i]-1]%MOD;

vector<int>prime={2,3,5,7,11, 13,17,19,23,29, 31,37,41,43,47, 53,59,61,67};
void solve()
{
  int n;cin>>n;
  vector<int>a(N),st(N);
  vector<ll>p(n+1);
  p[0]=1;
  for(int i=1;i<=n;++i)
  {
    int x;cin>>x;
    a[x]++;
    p[i]=(p[i-1]*2)%MOD;//ways to choose odd number or even number
  }
  for(int i=2;i<=70;++i)
  {
    int x=i;
    for(int j=0;j<prime.size();++j)
    {
      while(!(x%prime[j]))
      {
        st[i]^=(1<<j);
        x/=prime[j];
      }
    }
  }
  vector dp(71,vector<int>(1<<19));
  dp[0][0]=1;
  for(int i=1;i<=70;++i)
  {
    for(int j=0;j<(1<<18);++j)
    {
      if(!a[i])dp[i][j]=dp[i-1][j];
      else dp[i][j]=(dp[i-1][j]+dp[i-1][j^st[i]])%MOD*p[a[i]-1]%MOD;//choose odd or even
    }
  }
  cout<<(dp[70][0]-1+MOD)%MOD<<'\n';
  return;
}

2.线性🐔:

另外一种做法是基于线性🐔，我们考虑每个数能够贡献的对应质数的数的二进制位(即1<<19，每一位表示这个数含有奇数/偶数个该序号质数)

我们先预处理出对应的线性🐔，然后，这些线性基之间组合，不可能会出现完全平方数，这是因为都是0^1所以某一位永远是奇数，但是这些线性基和线性基之外的数组合，总有办法让对应位为0，基于这个性质，若线性🐔的数量为 s,那么对应的解应该为2^(n-s)

最后别忘了-1，减去一个数都不选择的情况

    struct LB
{
   vector<ll>p;
   int base;
   LB(int base=64)
   {
        p.resize(base);
        this->base=base;
   }   
   inline bool insert(ll x)
   {
        for(int i=base-1;i>=0;--i)
        {
            if(!(x>>i))continue;
            if(!p[i])
            {
                p[i]=x;
                break;
            }
            x^=p[i];
        }
        return x==0;
   }
   inline ll query(int x=0)
   {
        unsigned long long ans=0;
        for(int i=base-1;i>=0;--i)
        {
            ans=max(ans,ans^p[i]);
        }
        return ans;
   }
   void merge(const LB& aa)
   {
        for(int i=base-1;i>=0;--i)
        {
            if(aa.p[i])
            {
                insert(aa.p[i]);
            }
        }
   }
};
ll quick_pow(ll x,ll exp,int p)
{
      ll ans=1;
      while(exp)
      {
        if(exp&1)ans=ans*x%p;
        exp>>=1;
        x=x*x%p;
      }
      return ans;
}
vector<int>prime={2,3,5,7,11, 13,17,19,23,29, 31,37,41,43,47, 53,59,61,67};
void solve()
{
  LB lb(20);
  int n;cin>>n;
  for(int i=1;i<=n;++i)
  {
    int x;cin>>x;
    int now=0;
    for(int j=0;j<prime.size();++j)
    {
        now<<=1;
        while(!(x%prime[j]))
        {
            x/=prime[j];
            now^=1;
        }
    }
    lb.insert(now);
  }
  for(int i=lb.base-1;i>=0;--i)
  {
    n-=(lb.p[i]!=0);
  }
  cout<<quick_pow(2,n,MOD)-1<<'\n';
  return;
}

CF 985E

明明是2100但是最简单，这应该是最好想的一题了，首先我们把对应的值排序，然后使用尺取法进行遍历，比较简单，并且数据比较水，能直接过，过不了的话可以加数状数组优化

void solve()
{
  int n,k,d;
  cin>>n>>k>>d;
  vector<ll>a(n+1);
  for(int i=1;i<=n;++i)cin>>a[i];
  sort(a.begin()+1,a.end());
  vector<ll>dp(n+1);dp[0]=1;
  int r=1;
  for(int i=0;i<=n;++i)
  {
    if(dp[i]==0)continue;
    r=max(i+k,r);
    while(r<=n&&a[r]-a[i+1]<=d)
    {
        dp[r]=1;
        ++r;
    }
  }
  cout<<(dp[n]?"YES":"NO")<<'\n';
  return;
}

LOADING

dp practice_day 3