| ||||||||||
| 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