动态规划专题

\(A\) CF494C Helping People

\(B\) CF922E Birds

• 观察到 \(w\) 极大，正常的背包会 \(MLE\) 。

• 设 \(f_{i,j}\) 表示到第 \(i\) 棵树时一共召唤了 \(j\) 只小鸟时剩余的最大魔力值，状态转移方程为 \(f_{i,j}=\min(\max\limits_{k=0}^{\min(j,c_{i})} \{ f_{i-1,j-k}-cost_{i} \times k+x \},w+b \times j)\) ，边界为 \(f_{0,0}=w\) 。

  • 从 AT_dp_e Knapsack 2 中学到的套路。

• 最终，有 \(\max\limits_{i=0}^{\sum\limits_{j=1}^{n}c_{i}} \{ [f_{n,i} \ge 0] \times i \}\) 即为所求。

  点击查看代码

  ll c[10010],sum[10010],cost[10010],f[1010][10010];
  int main()
  {
      ll n,w,b,x,ans=0,i,j,k;
      cin>>n>>w>>b>>x;
      for(i=1;i<=n;i++)
      {
          cin>>c[i];
          sum[i]=sum[i-1]+c[i];
      }
      for(i=1;i<=n;i++)
      {
          cin>>cost[i];
      }
      memset(f,-0x3f,sizeof(f));
      f[0][0]=w;
      for(i=1;i<=n;i++)
      {
          for(j=0;j<=sum[i];j++)
          {
              for(k=0;k<=min(j,c[i]);k++)
              {
                  if(f[i-1][j-k]-cost[i]*k>=0)
                  {
                      f[i][j]=max(f[i][j],f[i-1][j-k]-cost[i]*k+x);
                  }
              }
              f[i][j]=min(f[i][j],w+b*j);
          }
      }
      for(i=sum[n];i>=0;i--)
      {
          if(f[n][i]>=0)
          {
              ans=i;
              break;
          }
      }
      cout<<ans<<endl;
      return 0;
  }  	  			 	       			 	 	
  

\(C\) CF285E Positions in Permutations

\(D\) CF1168D Anagram Paths

\(E\) CF573D Bear and Cavalry

\(F\) CF1392H ZS Shuffles Cards

\(G\) CF838C Future Failure

\(H\) CF536D Tavas in Kansas

\(I\) CF1628D1 Game on Sum (Easy Version)

• 设 \(x_{i}\) 表示第 \(i\) 轮时 Alice 选择的数。

• 设 \(f_{i,j}\) 表示已经进行了 \(i\) 轮，且使用了 \(j\) 次加法的最大得分，状态转移方程为 \(f_{i,j}=\frac{f_{i-1,j}+f_{i-1,j-1}}{2}\) ，边界为 \(\begin{cases} f_{i,0 \sim \infty}=0 & i=0 \\ f_{i,0}=0, f_{i,i}=i \times k & i \ne 0 \end{cases}\) 。

  • 由于 Bob 想让结果尽可能小，所以有 \(f_{i,j}= \min(f_{i-1,j}-x_{i},f_{i-1,j-1}+x_{i})\) 。
  • 由于 Alice 想让结果尽可能大，所以会让 \(\min(f_{i-1,j}-x_{i},f_{i-1,j-1}+x_{i})\) 取到最大值，即 \(f_{i-1,j}-x_{i}=f_{i-1,j-1}+x_{i}\) 时，解得 \(x_{i}= \frac{f_{i-1,j}-f_{i-1,j-1}}{2}\) ，代入原式有 \(f_{i,j}=\frac{f_{i-1,j}+f_{i-1,j-1}}{2}\) 。

• 由于 Bob 想让结果尽可能小，所以至多使用 \(m\) 次加法，故最终 \(f_{n,m}\) 即为所求。

• 另外，由于求解 \(f_{n,m}\) 的过程中只有加法和 \(\times \frac{1}{2}\) 运算，故可以将 \(k\) 缩小至 \(1\) 进行预处理 \(f_{n,m}\) ，询问时再扩大到 \(k\) （即 \(f_{n,m} \times k\) ）即可。

  点击查看代码

  const ll p=1000000007;
  ll f[2010][2010];
  ll qpow(ll a,ll b,ll p)
  {
      ll ans=1;
      while(b>0)
      {
          if(b&1)
          {
              ans=ans*a%p;
          }
          b>>=1;
          a=a*a%p;
      }
      return ans;
  }
  int main()
  {
      ll t,n,m,k,i,j;
      cin>>t;
      for(i=1;i<=2000;i++)
      {
          f[i][0]=0;
          f[i][i]=i;
          for(j=1;j<=i-1;j++)
          {
              f[i][j]=((f[i-1][j]+f[i-1][j-1])%p)*qpow(2,p-2,p)%p;
          }
      }
      for(i=1;i<=t;i++)
      {
          cin>>n>>m>>k;
          cout<<f[n][m]*k%p<<endl;
      }
      return 0;
  }