bzoj 5018 [Snoi2017]英雄联盟

题面

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

题解

简单的dp

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

那么

Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 ll read(){
 6     ll x=0,f=1;char c=getchar();
 7     while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
 8     while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
 9     return x*f;
10 }
11 
12 const int maxn=130;
13 ll n,m;
14 int num[maxn],cost[maxn];
15 ll dp[maxn][250000];
16 int ans=1e9;
17 
18 int main(){
19 #ifdef LZT
20     freopen("in","r",stdin);
21 #endif
22     n=read(),m=read();
23     for(int i=1;i<=n;i++) num[i]=read();
24     for(int i=1;i<=n;i++) cost[i]=read();
25     for(int i=1;i<=n;i++){
26         dp[i-1][0]=1;
27         for(int j=0;j<=249000;j++)
28             if(dp[i-1][j] && dp[i-1][j]<m){
29                 for(int k=0;k<=num[i] && dp[i-1][j]*(k-1)<m;k++)
30                     dp[i][j+k*cost[i]]=max(dp[i][j+k*cost[i]],dp[i-1][j]*(k?k:1));
31             }
32         for(int j=0;j<=249000;j++)
33             if(dp[i][j]>=m){
34                 ans=min(ans,j);
35                 break;
36             }
37     }
38     printf("%d
",ans);
39     return 0;
40 }
41 
42 /*
43 3 24
44 4 4 4
45 2 2 2
46 */