P9011 [USACO23JAN] Air Cownditioning II B　题解

Jorisy · 2023-02-04 18:30:07 · 题解

数据范围较小，易想到 dfs 暴力搜索。

首先对于输入的 s_i,t_i,c_i，我们开一个桶 cw，将对于 s_i\le\forall j\le t_i，执行 cw_j\leftarrow cw_j+c_i。

然后开始 dfs。

dfs 每次做选或不选，在第 dep 层选就是对于 a_{dep}\le\forall i\le b_{dep}，执行 cw_i\leftarrow cw_i-p_{dep}，然后价值 +m_{dep}。注意回溯。

然后搜完验证是否对于 1\le\forall i\le \max\{t_i\}，满足 cw_i\le 0 即可。

赛时 AC Code：

#include<bits/stdc++.h>
using namespace std;

int n,m,k,ans=1e9,cw[105],s[25],t[25],c[25],a[25],b[25],p[25],v[25];

bool f()//是否满足
{
    for(int i=1;i<=k;i++)
    {
        if(cw[i]>0) return 0;
    }
    return 1;
}

void dfs(int dep,int s)
{
    if(dep>m)
    {
        //cerr<<"DE: ";for(int i=1;i<=k;i++) cerr<<cw[i]<<' ';cerr<<endl;
        if(f()) ans=min(ans,s);//合法就更新答案
        return;
    }
    dfs(dep+1,s);//不选
    for(int i=a[dep];i<=b[dep];i++) cw[i]-=p[dep];
    dfs(dep+1,s+v[dep]);//选
    for(int i=a[dep];i<=b[dep];i++) cw[i]+=p[dep];//回溯
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i]>>t[i]>>c[i];
        k=max(k,t[i]);
        for(int j=s[i];j<=t[i];j++) cw[j]+=c[i];//事先处理
    }
    for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>p[i]>>v[i];
    dfs(1,0);
    cout<<ans;
    return 0;
}