3.分宿舍:
看到这个题,就想到了讨论,然后数学数学数学....讨论蒙蔽了
题解做法:
(1)枚举:
因为肯定要住一定量的双人间,三人间和情侣间,所以枚举情侣间的数量,然后枚举住双人间的人数进而得出要住多少双人间,然后可以计算出住多少三人间(如果枚举双人间的数量的话,还要考虑是否住满的情况,讨论一下才能得出三人间的数量,(枚举三人间的数量要讨论的情况更多),所以枚举人数)复杂度O(n^2)
(2)背包:
物品体积为2/3的背包,然后再转移一下情侣间的数量就好了,复杂度O(n)
枚举做法:
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 int n,m,k,a,b,c; 5 const ll inf=1e18; 6 const int maxn=1e3+3; 7 void solve() 8 { 9 int n,m,k;ll a,b,c; 10 cin>>n>>m>>k>>a>>b>>c; 11 ll ans=inf; 12 for(int i=0;i<=k;++i)//枚举情侣间 13 { 14 int boy=n+k-i;//住非情侣间的男生 15 int girl=m+k-i;//住非情侣间的女生 16 ll cost1=i*c; 17 ll cost2=inf,cost3=inf; 18 for(int j=0;j<=boy;++j)//枚举男生 19 { 20 int two=ceil(j*1.0/2);//双人间数量 21 int three=ceil((boy-j)*1.0/3);//三人间数量 22 cost2=min(1ll*two*a+1ll*three*b,cost2); 23 } 24 int q=1; 25 for(int j=0;j<=girl;++j)//女生相同 26 { 27 int two=ceil(j*1.0/2); 28 int three=ceil((girl-j)*1.0/3); 29 cost3=min(1ll*two*a+1ll*three*b,cost3); 30 } 31 ans=min(ans,cost1+cost2+cost3);//情侣房价钱+男生价钱+女生价钱 32 } 33 cout<<ans<<endl; 34 } 35 int main() 36 { 37 int t;cin>>t; 38 while(t--) solve(); 39 }
背包代码:
#include<bits/stdc++.h> #define ll long long using namespace std; void solve() { int n,m,k;ll a,b,c; cin>>n>>m>>k>>a>>b>>c; ll dp[4000]; for(int i=0;i<4000;++i) dp[i]=1e18; dp[0]=0;dp[1]=dp[2]=min(a,b);//初始化一下 for(int i=3;i<=n+m+k+10;++i) { dp[i]=min(dp[i-2]+a,dp[i-3]+b); } ll ans=1e18; for(int i=0;i<=k;++i) { ans=min(ans,i*c+dp[n+k-i]+dp[m+k-i]);//对情侣间数量进行下转移 } cout<<ans<<endl; } int main() { int t; cin>>t; for(int i=1;i<=t;++i) { solve(); } }
原文：https://www.cnblogs.com/codeoosacm/p/10731319.html