bzoj 5018 [Snoi2017]英雄联盟

时间：2022-03-07 13:52:38

题面

https://www.lydsy.com/JudgeOnline/problem.php?id=5018

题解

简单的dp

令dp[i][j]表示前i个英雄 总花费为j 最大能够得到的展示种数

那么bzoj 5018 [Snoi2017]英雄联盟

Code

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll read(){

     ll x=,f=;char c=getchar();

     while(c<'' || c>''){if(c=='-')f=-;c=getchar();}

     while(c>='' && c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 const int maxn=;

 ll n,m;

 int num[maxn],cost[maxn];

 ll dp[maxn][];

 int ans=1e9;

 int main(){

 #ifdef LZT

     freopen("in","r",stdin);

 #endif

     n=read(),m=read();

     for(int i=;i<=n;i++) num[i]=read();

     for(int i=;i<=n;i++) cost[i]=read();

     for(int i=;i<=n;i++){

         dp[i-][]=;

         for(int j=;j<=;j++)

             if(dp[i-][j] && dp[i-][j]<m){

                 for(int k=;k<=num[i] && dp[i-][j]*(k-)<m;k++)

                     dp[i][j+k*cost[i]]=max(dp[i][j+k*cost[i]],dp[i-][j]*(k?k:));

             }

         for(int j=;j<=;j++)

             if(dp[i][j]>=m){

                 ans=min(ans,j);

                 break;

             }

     }

     printf("%d\n",ans);

     return ;

 }

 /*

 3 24

 4 4 4

 2 2 2

 */

相关文章