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 |
时间o(n*n) ,空间o(n)表示实在无法理解怎么可能内存不够。。 先对n个人按时间排序 dp[i]表示第i个人成功进步得到的最高分。。。注意是成功! 那则必然从dp[j]转移过来的 。。0<=j <i 然后没了。。 #include<cstdio> #include<algorithm> using namespace std; struct gangster{ int t , s ,p; }a[105]; int dp[105],n,k,t; bool cmp( gangster a , gangster b ){ return a.t < b.t;} int main() { scanf("%d%d%d",&n,&k,&t); a[0].t = a[0].s = a[0].p = 0; for (int i = 1; i<=n; i++) scanf("%d",&a[i].t ); for (int i = 1; i<=n; i++) scanf("%d",&a[i].p ); for (int i = 1; i<=n; i++) scanf("%d",&a[i].s ); sort( a , a+n+1 , cmp ); int ans = 0; for (int i = 1; i<=n; i++) { if ( a[i].t > t ) break; for (int j = 0; j<i; j++) { if ( dp[j] == 0 && j!= 0 ) continue; if ( abs( a[i].t - a[j].t ) < abs( a[i].s - a[j].s ) ) continue; dp[i] = max ( dp[i] , dp[j] + a[i].p ); } ans = max( ans , dp[i] ); } printf("%d\n",ans); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator