首页 > 代码库 > BZOJ1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚
BZOJ1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚
1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 414 Solved: 191
[Submit][Status]
Description
Farmer John‘s cows, pampered since birth, have reached new heights of fastidiousness. They now require their barn to be immaculate. Farmer John, the most obliging of farmers, has no choice but hire some of the cows to clean the barn. Farmer John has N (1 <= N <= 10,000) cows who are willing to do some cleaning. Because dust falls continuously, the cows require that the farm be continuously cleaned during the workday, which runs from second number M to second number E during the day (0 <= M <= E <= 86,399). Note that the total number of seconds during which cleaning is to take place is E-M+1. During any given second M..E, at least one cow must be cleaning. Each cow has submitted a job application indicating her willingness to work during a certain interval T1..T2 (where M <= T1 <= T2 <= E) for a certain salary of S (where 0 <= S <= 500,000). Note that a cow who indicated the interval 10..20 would work for 11 seconds, not 10. Farmer John must either accept or reject each individual application; he may NOT ask a cow to work only a fraction of the time it indicated and receive a corresponding fraction of the salary. Find a schedule in which every second of the workday is covered by at least one cow and which minimizes the total salary that goes to the cows.
Input
* Line 1: Three space-separated integers: N, M, and E. * Lines 2..N+1: Line i+1 describes cow i‘s schedule with three space-separated integers: T1, T2, and S.
Output
* Line 1: a single integer that is either the minimum total salary to get the barn cleaned or else -1 if it is impossible to clean the barn.
Sample Input
0 2 3 //一号牛,从0号stall打扫到2号,工资为3
3 4 2
0 0 1
INPUT DETAILS:
FJ has three cows, and the barn needs to be cleaned from second 0 to second
4. The first cow is willing to work during seconds 0, 1, and 2 for a total
salary of 3, etc.
Sample Output
HINT
约翰有3头牛，牛棚在第0秒到第4秒之间需要打扫．第1头牛想要在第0，1，2秒内工作，为此她要求的报酬是3美元．其余的依此类推． 约翰雇佣前两头牛清扫牛棚，可以只花5美元就完成一整天的清扫．
Source
Silver
题解：
这道题不错，线段树优化DP。
按照l端点排序牛
f[i]表示到i时刻的最小代价，那么对于一只l-r费用c的牛
可以用f[i-1]+c更新l-r
用线段树维护，单点查询，区间更新
代码：
（不知道哪里写残了T_T）
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 100000000000 24 25 #define maxn 80000+2000 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 61 struct rec{int l,r;ll w;}a[maxn]; 62 63 struct seg{int l,r;ll mi,tag;}t[4*maxn]; 64 65 int n,x,y; 66 67 inline bool cmp(rec a,rec b) 68 69 { 70 71 return a.l<b.l||(a.l==b.l&&a.r<b.r); 72 73 } 74 75 inline void pushup(int k) 76 77 { 78 79 t[k].mi=min(t[k<<1].mi,t[k<<1|1].mi); 80 81 } 82 83 inline void update(int k,ll z) 84 85 { 86 87 t[k].mi=min(t[k].mi,z); 88 89 t[k].tag=min(t[k].tag,z); 90 91 } 92 93 inline void pushdown(int k) 94 95 { 96 97 if(t[k].tag==-1)return ; 98 99 update(k<<1,t[k].tag);100 101 update(k<<1|1,t[k].tag);102 103 t[k].tag=-1;104 105 }106 107 inline void build(int k,int x,int y)108 109 {110 111 int l=t[k].l=x,r=t[k].r=y,mid=(l+r)>>1;t[k].tag=-1;112 113 if(l==r){t[k].mi=l==0?0:inf;return ;}114 115 build(k<<1,l,mid);build(k<<1|1,mid+1,r);116 117 pushup(k);118 119 }120 121 inline ll query(int k,int x)122 123 {124 125 int l=t[k].l,r=t[k].r,mid=(l+r)>>1;126 127 if(l==r)return t[k].mi;128 129 pushdown(k);130 131 if(x<=mid)return query(k<<1,x);else return query(k<<1|1,x);132 133 }134 135 inline void change(int k,int x,int y,ll z)136 137 {138 139 int l=t[k].l,r=t[k].r,mid=(l+r)>>1;140 141 if(l==x&&r==y){update(k,z);return;}142 143 pushdown(k);144 145 if(y<=mid)change(k<<1,x,y,z);146 147 else if(x>mid)change(k<<1|1,x,y,z);148 149 else change(k<<1,x,mid,z),change(k<<1|1,mid+1,y,z);150 151 pushup(k);152 153 }154 155 int main()156 157 {158 159 freopen("input.txt","r",stdin);160 161 freopen("output.txt","w",stdout);162 163 n=read();x=read();y=read();164 165 for1(i,n)166 167 {168 169 a[i].l=read()-x+1;a[i].r=read()-x+1;a[i].w=read();170 171 if(a[i].l<=0)a[i].l=1;172 173 }174 175 sort(a+1,a+n+1,cmp);176 177 build(1,0,y-x+1);178 179 for1(i,n)180 181 {182 183 if(a[i].r<a[i].l)continue;184 185 if(a[i].r<=0)continue;186 187 if(a[i].l>y-x+1)continue;188 189 ll t=query(1,a[i].l-1);190 191 if(t!=inf)change(1,a[i].l,min(a[i].r,y-x+1),t+a[i].w);else break;192 193 }194 195 //for1(i,n)cout<<a[i].l<<‘ ‘<<a[i].r<<‘ ‘<<a[i].w<<endl;196 197 //for1(k,8*n)cout<<t[k].l<<‘ ‘<<t[k].r<<‘ ‘<<t[k].mi<<‘ ‘<<t[k].tag<<endl;198 199 ll ans=query(1,y-x+1);200 201 printf("%lld\n",ans==inf?-1:ans);202 203 return 0;204 205 }
hzwer的
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #define ll long long 7 #define inf 10000000000 8 using namespace std; 9 inline ll read()10 {11 int x=0,f=1;char ch=getchar();12 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14 return x*f;15 }16 int n,bg,ed;17 struct seg{int l,r;ll tag,mn;}t[400005];18 struct data{int t1,t2,c;}a[10005];19 inline bool operator<(data a,data b)20 {21 return a.t1<b.t1;22 }23 void pushdown(int k)24 {25 if(t[k].l==t[k].r)return;26 ll tag=t[k].tag;t[k].tag=inf;27 if(tag!=inf)28 {29 t[k<<1].tag=min(t[k<<1].tag,tag);30 t[k<<1|1].tag=min(t[k<<1|1].tag,tag);31 t[k<<1].mn=min(t[k<<1].mn,tag);32 t[k<<1|1].mn=min(t[k<<1|1].mn,tag);33 }34 }35 void build(int k,int l,int r)36 {37 t[k].l=l;t[k].r=r;t[k].mn=inf;t[k].tag=inf;38 if(l==r)return;39 int mid=(l+r)>>1;40 build(k<<1,l,mid);build(k<<1|1,mid+1,r);41 }42 ll query(int k,int x)43 {44 pushdown(k);45 if(x<bg)return 0;46 int l=t[k].l,r=t[k].r;47 if(l==r)return t[k].mn;48 int mid=(l+r)>>1;49 if(x<=mid)return query(k<<1,x);50 else return query(k<<1|1,x);51 }52 void update(int k,int x,int y,ll val)53 {54 pushdown(k);55 int l=t[k].l,r=t[k].r;56 if(x==l&&y==r)57 {58 t[k].tag=val;59 t[k].mn=min(t[k].mn,val);60 return;61 }62 int mid=(l+r)>>1;63 if(y<=mid)update(k<<1,x,y,val);64 else if(x>mid)update(k<<1|1,x,y,val);65 else66 {67 update(k<<1,x,mid,val);68 update(k<<1|1,mid+1,y,val);69 }70 }71 int main()72 {73 n=read();bg=read();ed=read();74 build(1,bg,ed);75 for(int i=1;i<=n;i++)76 a[i].t1=read(),a[i].t2=read(),a[i].c=read();77 sort(a+1,a+n+1);78 for(int i=1;i<=n;i++)79 {80 int t1=a[i].t1,t2=a[i].t2,c=a[i].c;81 ll tmp=query(1,t1-1);82 if(tmp==inf){puts("-1");return 0;}83 update(1,t1,t2,tmp+c);84 }85 ll ans=query(1,ed);86 if(ans<inf)printf("%lld",ans);87 else puts("-1");88 return 0;89 }
BZOJ1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚