天梯选拔赛第一场

whatdo / 2024-03-06 / 原文

B 孵化小鸡 - SMUOJ

题解：因为数据很小我们可以枚举每一个状态然后判断一下是否可以达到孵化的温度即可

我们用二进制枚举，一共1<<m相当于2的m次方，用二进制枚举每一个状态

//#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;

int biao[N];
PII c[N];
int k[N];
int p[N];

void solve()
{
    int n,m;
    cin>>n>>m;
    int zz=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,mi;
        cin>>a>>b>>mi;
        zz=max(zz,b);
        for(int j=a;j<=b;j++)
        {
            biao[j]=mi;
        }
    }
    for(int i=0;i<m;i++)
    {
        int l,r,ki,pi;
        cin>>l>>r>>ki>>pi;
        c[i]={l,r};
        k[i]=ki;
        p[i]=pi;
    }
    int ans=0;
    int sum=INF;
    for(int i=0;i<1<<m;i++)
    {
        ans=0;
        int op[N]={0};
       for(int j=0;j<m;j++)
       {
           if(i&1<<j)   //判断这一位是否是开启的状态
           {
               ans+=p[j];
               for(int ea=c[j].first;ea<=c[j].second;ea++)
               {
                   op[ea]+=k[j];
               }
           }
       }
       int f=0;
       for(int j=1;j<=zz;j++)
       {
           if(biao[j]==0) continue;
           else
           {

               if(biao[j]>op[j])
               {
                   f=1;
                   break;
               }
           }
       }
       if(!f)
       {
           sum=min(sum,ans);
       }
    }
    cout<<sum<<endl;
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

下面写另外一个暴力搜索的版本

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5,M=1e9+7;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> PII;
int n,m;
int biao[N]={0};
struct G
{
    int l,r;
    int k,p;
}a[N];
int ans=INF;
void dfs(int dep,bool op,int p)
{
    if(dep>m) return;
    if(op)
    {
        p+=a[dep].p;
        int cnt=0;
        for(int i=1;i<=100;i++)
        {
            if(i>=a[dep].l && i<=a[dep].r) biao[i]-=a[dep].k;
            if(biao[i]<=0) cnt++;
        }
        if(cnt==100)
        {
            ans=min(ans,p);
            return;
        }
        dfs(dep+1,1,p);
        for(int i=a[dep+1].l;i<=a[dep+1].r;i++)
        {
            biao[i]+=a[dep+1].k;
        }
        dfs(dep+1,0,p);
    }
    else
    {
        dfs(dep+1,1,p);
        for(int i=a[dep+1].l;i<=a[dep+1].r;i++)
        {
            biao[i]+=a[dep+1].k;
        }
        dfs(dep+1,0,p);

    }
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int l,r,val;
        cin>>l>>r>>val;
        for(int j=l;j<=r;j++)
        {
            biao[j]=val;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,k,p;
        cin>>l>>r>>k>>p;
        a[i]={l,r,k,p};
    }
    dfs(1,1,0);
    for(int i=a[1].l;i<=a[1].r;i++) biao[i]+=a[1].k;
    dfs(1,0,0);
    cout<<ans<<endl;
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}