大家求的USACO铜 T2题解
本帖最后由 ExiaGN001 于 2023-2-3 08:43 编辑数位dp即可。
题目：
2.空调
Farmer John 的农场经历了有史以来最热的夏天，他需要一种方法来为他的奶牛降温。因此，他决定投资购买一些空调。
农夫约翰的N只奶牛（1≤N≤ 20) 住在一个谷仓里，谷仓里有一系列连续的位置，编号1 到100.第i头牛占据了从s[ i]开始直到t[ i]的所有位置. 不同奶牛占据的位置都是相互不相交的。
奶牛有不同的冷却要求。第i头牛必须获得c[ i]的冷却量, 意思是牛占据的每个位置必须至少降低其温度c个单位。
谷仓有m台空调，标有1 ~m的编号 (1≤M≤ 10). 第i台空调的运作成本是m[ i]（1≤ m≤ 1000) 。第i台空调可以使a[ i]到b 的区域的温度降低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
复制代码
一种花费最少的可能解决方案是选择那些可以冷却这些区域:,， 和，成本为3+2+5=10.
题目提供者：Aryansh Shrivastava 和 Eric Hsu,感谢他们的贡献。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int s,t,c;
int m2,a,b,p;
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;
int tmpc;
for(int i=0;i<n;i++)
tmpc=c;
int tmpans=0;
for(int i=1;i<=m;i++)
{
ch=(idx>>(n-i))%2;
}
for(int i=0;i<m;i++)
{
if(ch)
{
tmpans+=m2;
for(int j=0;j<n;j++)
{
if(cross(s,t,a,b))
{
tmpc-=p;
}
}
}
}
bool flg=1;
for(int i=0;i<n;i++)
{
if(tmpc>0)return ;
}
ans=min(ans,tmpans);
return ;
}
//m=10可以递归做/数位动态规划
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>s>>t>>c;
for(int i=0;i<m;i++)cin>>a>>b>>p>>m2;
int siz=pow(2,m);//不超过1024
for(int i=0;i<siz;i++)
{
check(i);
}
cout<<ans;
}
牛牛{:10_256:}{:10_256:}{:10_256:} 老实用深搜吧，毕竟 210 也就只有 1024 左右{:10_291:} zhangjinxuan 发表于 2023-2-6 19:12
老实用深搜吧，毕竟 2 也就只有 1024 左右
对滴，数位dp和DFS都对数据量有要求 ExiaGN001 发表于 2023-2-6 19:28
对滴，数位dp和DFS都对数据量有要求
我怕出事{:5_99:}
页:
[1]