这道题本身只是一道比较水的dp,但是……它会卡O(n^2)的算法!!!
所以,我们可以用数据结构优化!我用的线段树(单修区查多好写呀)
要注意几点:
1.dp数组在起点要清零
2.循环取最小值时是从t[i].l-1到t[i].r
3.线段树minn要取最大
4.区间排序按右端点排
先上70分代码(我先得了100分为了题解再亲测了一遍70……)
#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define ll long long using namespace std; const int INF=0x3f3f3f3f,MAXX=100000; int n,l,r; int cnt; int dp[MAXX+5]; struct node{int l,r,v;}t[MAXX+5]; bool cmp(node x,node y){return x.r<y.r;}//按右端点从小到大排序 int main() { scanf("%d %d %d",&n,&l,&r); for(int i=1;i<=n;i++) { int x,y,z; scanf("%d %d %d",&x,&y,&z); if(x<l)x=l;if(y>r)y=r;//不知道有没有,但是为了以防万一还是写上了 if(x>y)continue;//同上 t[++cnt].l=x;t[cnt].r=y;t[cnt].v=z; } sort(t+1,t+cnt+1,cmp); memset(dp,0x3f,sizeof(dp));//dp数组清最大值 dp[l]=0;//左端点初值 for(int i=1;i<=cnt;i++) { int k=INF; for(int j=t[i].l-1;j<=t[i].r;j++)k=min(k,dp[j]);//从t[i].l-1——t[i].r dp[t[i].r]=min(dp[t[i].r],k+t[i].v);//更新 } if(dp[r]==INF)printf("-1");//如果最后值为INF说明中间必定有时间打扫不到,输出-1 else printf("%d",dp[r]); return 0; }
满分代码
#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define ll long long using namespace std; const int INF=0x3f3f3f3f,MAXX=100000; int delta=10; int n,l,r; int cnt; int dp[MAXX+5]; struct tree{int l,r,minn;}tree[MAXX*8+5]; struct node{int l,r,v;}t[MAXX+5]; bool cmp(node x,node y){return x.r<y.r;}//按右端点从小到大排序 void Build(int k,int l,int r) { tree[k].l=l;tree[k].r=r;tree[k].minn=INF;//线段树最小值清最大 if(l==r){return;} int mid=(l+r)>>1; Build(k<<1,l,mid); Build(k<<1|1,mid+1,r); } void add(int k,int x,int v) { if(x<tree[k].l||x>tree[k].r)return; tree[k].minn=min(tree[k].minn,v); int mid=(tree[k].l+tree[k].r)>>1; add(k<<1,x,v);add(k<<1|1,x,v); } int ask(int k,int l,int r) { int ans=INF; if(l<=tree[k].l&&r>=tree[k].r)return tree[k].minn; int mid=(tree[k].l+tree[k].r)>>1; if(l<=mid)ans=min(ans,ask(k<<1,l,r)); if(r>mid)ans=min(ans,ask(k<<1|1,l,r)); return ans; }//模版线段树单修区查 int main() { Build(1,1,100000);//按数据范围建树 scanf("%d %d %d",&n,&l,&r); l+=10;r+=10;//全部加一个小数,不然会玄学RE for(int i=1;i<=n;i++) { int x,y,z; scanf("%d %d %d",&x,&y,&z); x+=10;y+=10; if(x<l)x=l;if(y>r)y=r;//不知道有没有,但是为了以防万一还是写上了 if(x>y)continue;//同上 t[++cnt].l=x;t[cnt].r=y;t[cnt].v=z; } sort(t+1,t+cnt+1,cmp); memset(dp,0x3f,sizeof(dp));//dp数组清最大值 dp[l]=0;//左端点初值 add(1,l,0);//更新到线段树里 for(int i=1;i<=cnt;i++) { int k=INF; k=min(k,ask(1,t[i].l-1,t[i].r));//从t[i].l-1——t[i].r // cout<<1; dp[t[i].r]=min(dp[t[i].r],k+t[i].v);//更新的同时更新到线段树里 add(1,t[i].r,dp[t[i].r]); // cout<<2; } if(dp[r]==INF)printf("-1");//如果最后值为INF说明中间必定有时间打扫不到,输出-1 else printf("%d",dp[r]); return 0; }