Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
怎么过的……帮我看看……In Reply To:N^2暴力也过。 Posted by:jsn1993 at 2009-09-26 20:03:10 #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int inf=1<<30; int n,e,t,f[90000]; struct qwq{ int l,r,c; }ti[10050]; bool cmp(const qwq&a,const qwq&b){ return a.r<b.r; } bool yes=true; int main(){ scanf("%d%d%d",&n,&e,&t); for(int i=1;i<=n;++i){ scanf("%d%d%d",&ti[i].l ,&ti[i].r ,&ti[i].c ); if(ti[i].l <=e) yes=false; } sort(ti+1,ti+n+1,cmp); if(ti[n].r <n||yes==true){//kacha cout<<"-1"<<endl; return 0; } for(int i=1;i<=ti[n].r ;++i) f[i]=inf;// f[e-1]=0; for(int i=1;i<=n;++i){ int minn=inf; for(int x=ti[i].l -1;x<ti[i].r ;++x){ minn=min(minn,f[x]); } f[ti[i].r ]=min(minn+ti[i].c ,f[ti[i].r ]); } int ans=inf; for(int i=t;i<=ti[n].r ;++i) ans=min(ans,f[i]); if(ans!=inf) cout<<ans<<endl; else cout<<"-1"<<endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator