2050部分题解

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();
    }
}

　　一眼看出来是dp,因为体力范围是1e9,所以不能用体力来dp,可定义

　　dp[i][j]={前i个挑战中接受了j个挑战后剩余体力的最大值},我们要然这个值尽可大

　　所以dp转移方程就出来了:

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

　　(然而出来转移方程有什么用呢,边界,细节考虑不好好不是一样凉凉嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤)

　　代码如下:

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int maxn=1e3+3;
 5 int n;ll hp;
 6 ll dp[maxn][maxn];
 7 void solve()
 8 {
 9     memset(dp,0,sizeof(dp));
10     cin>>n>>hp;
11     ll a[maxn],b[maxn],c[maxn];
12     for(int i=1;i<=n;++i) cin>>a[i]>>b[i]>>c[i];
13     dp[0][0]=hp;
14     for(int i=1;i<=n;++i) dp[i][0]=dp[i-1][0]+c[i];
15     for(int i=1;i<=n;++i)
16     {
17         for(int j=1;j<=i;++j)
18         {
19             if(dp[i-1][j]) dp[i][j]=max(dp[i][j],dp[i-1][j]+c[i]);//其实可以写成
20                                                                   //dp[i][j]=dp[i-1][j]+c[i]
21                                                                   //因为在此之前,dp[i][j]从未更新过,更新后肯定变大
22             if(min(dp[i-1][j-1],b[i])>a[i])
23             {
24                 dp[i][j]=max( min(dp[i-1][j-1],b[i]) -a[i]+c[i],dp[i][j]);
25             }
26 //            一个错误版本:
27 //            if(min(dp[i-1][j-1],b[i])-a[i]>0 && dp[i-1][j])
28 //            {
29 //                dp[i][j]=max( min(dp[i-1][j-1],b[i])-a[i],dp[i-1][j] )+c[i]; //尝试直接根据转移式来比较,错误,因为dp
30 //            }                                                                //开始的时候dp[i-1][j]一直为0,只有经过一次
31 //                                                                             //第29行的转移式才不为0
32 //            else if(dp[i-1][j]) dp[i][j]=dp[i-1][j]+c[i];
33 //
34         }
35     }
36     for(int i=n;i>=0;--i) if(dp[n][i]) {cout<<i<<endl;
37             return;}
38 }
39 int main()
40 {
41     ios::sync_with_stdio(0);
42     int t;cin>>t;
43     while(t--)solve();
44 }