大家求的USACO铜 T2题解

ExiaGN001

数位dp即可。

题目：

2.空调
Farmer John 的农场经历了有史以来最热的夏天，他需要一种方法来为他的奶牛降温。因此，他决定投资购买一些空调。

农夫约翰的N只奶牛（1≤N≤ 20) 住在一个谷仓里，谷仓里有一系列连续的位置，编号1 到100.第i头牛占据了从s[ i]开始直到t[ i]的所有位置. 不同奶牛占据的位置都是相互不相交的。
奶牛有不同的冷却要求。第i头牛必须获得c[ i]的冷却量, 意思是牛占据的每个位置必须至少降低其温度c[i ]个单位。

谷仓有m台空调，标有1 ~m的编号 (1≤M≤ 10). 第i台空调的运作成本是m[ i]（1≤ m[i ]≤ 1000) 。第i台空调可以使a[ i]到b [i ]的区域的温度降低p[ i]度（1≤ p[ i]≤10^6).
空调覆盖的区域可能会重叠。

经营农场绝非易事，因此 FJ 的预算很紧。
请确定他至少需要花多少钱才能让他所有的奶牛都感到舒适。
可以保证，如果 FJ 使用他所有的空调，那么所有的奶牛都会感到舒适。

输入格式（输入来自终端/stdin）：
1行输入 n,m.
2~n+1行描述奶牛。第i+1行的三个数分别是s[ i],t[ i],c[ i]的值。
n+2~n+m+1行描述空调。第i+n+1行的四个数分别是a[ i],b[ i],p[ i],m[ i]的值。
除了两个输入样例之外的其他样例都满足m=10。

输出格式（打印输出到终端/stdout）：
输出一个整数，告诉 FJ 需要花费最少的钱来运行足够的空调来满足他所有的奶牛（在上面列出的条件下）。

样例输入：
2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5
复制代码

样例输出：
10
复制代码

一种花费最少的可能解决方案是选择那些可以冷却这些区域:[2,9],[1,2]， 和[6,9]，成本为3+2+5=10.

题目提供者：Aryansh Shrivastava 和 Eric Hsu,感谢他们的贡献。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int s[25],t[25],c[25];
int m2[15],a[15],b[15],p[15];
int ans=2147483647;
bool cross(int al,int ar,int bl,int br)
{
    if(ar<bl || br<al)//前不见古人，后不见来者
        return 0;
    else return 1;

}
void check(int idx)
{
    int ch[15];
    int tmpc[25];
    for(int i=0;i<n;i++)
        tmpc[i]=c[i];
    int tmpans=0;
    for(int i=1;i<=m;i++)
    {
        ch[i-1]=(idx>>(n-i))%2;
    }
    for(int i=0;i<m;i++)
    {
        if(ch[i])
        {
            tmpans+=m2[i];
            for(int j=0;j<n;j++)
            {
                if(cross(s[i],t[i],a[i],b[i]))
                {
                    tmpc[i]-=p[i];
                }
            }
        }
    }
    bool flg=1;
    for(int i=0;i<n;i++)
    {
        if(tmpc[i]>0)return ;
    }
    ans=min(ans,tmpans);
    return ;
}

//m=10可以递归做/数位动态规划
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>s[i]>>t[i]>>c[i];
    for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>p[i]>>m2[i];
    int siz=pow(2,m);//不超过1024

    for(int i=0;i<siz;i++)
    {
        check(i);
    }
    cout<<ans;
}

Mike_python小

牛牛

zhangjinxuan

老实用深搜吧，毕竟 2¹⁰ 也就只有 1024 左右

ExiaGN001

zhangjinxuan 发表于 2023-2-6 19:12
老实用深搜吧，毕竟 2 也就只有 1024 左右

对滴，数位dp和DFS都对数据量有要求

zhangjinxuan

ExiaGN001 发表于 2023-2-6 19:28
对滴，数位dp和DFS都对数据量有要求

我怕出事