大家求的USACO铜 T2题解

ExiaGN001

数位dp即可。

题目：

1. 2.空调
   
2. Farmer John 的农场经历了有史以来最热的夏天，他需要一种方法来为他的奶牛降温。因此，他决定投资购买一些空调。
   
3. 
   
4. 农夫约翰的N只奶牛（1≤N≤ 20) 住在一个谷仓里，谷仓里有一系列连续的位置，编号1 到100.第i头牛占据了从s[ i]开始直到t[ i]的所有位置. 不同奶牛占据的位置都是相互不相交的。
   
5. 奶牛有不同的冷却要求。第i头牛必须获得c[ i]的冷却量, 意思是牛占据的每个位置必须至少降低其温度c[i ]个单位。
   
6. 
   
7. 谷仓有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).
   
8. 空调覆盖的区域可能会重叠。
   
9. 
   
10. 经营农场绝非易事，因此 FJ 的预算很紧。
    
11. 请确定他至少需要花多少钱才能让他所有的奶牛都感到舒适。
    
12. 可以保证，如果 FJ 使用他所有的空调，那么所有的奶牛都会感到舒适。
    
13. 
    
14. 输入格式（输入来自终端/stdin）：
    
15. 1行输入 n,m.
    
16. 2~n+1行描述奶牛。第i+1行的三个数分别是s[ i],t[ i],c[ i]的值。
    
17. n+2~n+m+1行描述空调。第i+n+1行的四个数分别是a[ i],b[ i],p[ i],m[ i]的值。
    
18. 除了两个输入样例之外的其他样例都满足m=10。
    
19. 
    
20. 输出格式（打印输出到终端/stdout）：
    
21. 输出一个整数，告诉 FJ 需要花费最少的钱来运行足够的空调来满足他所有的奶牛（在上面列出的条件下）。
    
22. 
    
23. 样例输入：
    
24. 2 4
    
25. 1 5 2
    
26. 7 9 3
    
27. 2 9 2 3
    
28. 1 6 2 8
    
29. 1 2 4 2
    
30. 6 9 1 5
    
31. 复制代码
    
32. 
    
33. 样例输出：
    
34. 10
    
35. 复制代码
    
36. 
    
37. 一种花费最少的可能解决方案是选择那些可以冷却这些区域:[2,9],[1,2]， 和[6,9]，成本为3+2+5=10.
    
38. 
    
39. 题目提供者：Aryansh Shrivastava 和 Eric Hsu,感谢他们的贡献。

复制代码

代码：

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int n,m;
   
4. int s[25],t[25],c[25];
   
5. int m2[15],a[15],b[15],p[15];
   
6. int ans=2147483647;
   
7. bool cross(int al,int ar,int bl,int br)
   
8. {
   
9.     if(ar<bl || br<al)//前不见古人，后不见来者
   
10.         return 0;
    
11.     else return 1;
    
12. 
    
13. }
    
14. void check(int idx)
    
15. {
    
16.     int ch[15];
    
17.     int tmpc[25];
    
18.     for(int i=0;i<n;i++)
    
19.         tmpc[i]=c[i];
    
20.     int tmpans=0;
    
21.     for(int i=1;i<=m;i++)
    
22.     {
    
23.         ch[i-1]=(idx>>(n-i))%2;
    
24.     }
    
25.     for(int i=0;i<m;i++)
    
26.     {
    
27.         if(ch[i])
    
28.         {
    
29.             tmpans+=m2[i];
    
30.             for(int j=0;j<n;j++)
    
31.             {
    
32.                 if(cross(s[i],t[i],a[i],b[i]))
    
33.                 {
    
34.                     tmpc[i]-=p[i];
    
35.                 }
    
36.             }
    
37.         }
    
38.     }
    
39.     bool flg=1;
    
40.     for(int i=0;i<n;i++)
    
41.     {
    
42.         if(tmpc[i]>0)return ;
    
43.     }
    
44.     ans=min(ans,tmpans);
    
45.     return ;
    
46. }
    
47. 
    
48. //m=10可以递归做/数位动态规划
    
49. int main()
    
50. {
    
51.     cin>>n>>m;
    
52.     for(int i=0;i<n;i++)cin>>s[i]>>t[i]>>c[i];
    
53.     for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>p[i]>>m2[i];
    
54.     int siz=pow(2,m);//不超过1024
    
55. 
    
56.     for(int i=0;i<siz;i++)
    
57.     {
    
58.         check(i);
    
59.     }
    
60.     cout<<ans;
    
61. }
    

复制代码

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都对数据量有要求

我怕出事