| ||||||||||
| 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 | |||||||||
能不能哪位大神帮我看下这段代码超时的原因?/*
谢谢了!
*/
//poj 2355
//dp 由前向后dp
#include <iostream>
#include <limits>
#include <algorithm>
using namespace std;
const int MAX = 10005;
#define MIN(a,b) ((a)<(b))?(a):(b)
int d[MAX];
int L1,L2,L3,C1,C2,C3;
int N;
int start, end;
int dp[MAX];
int main()
{
//memset(dp,0x7F,sizeof(dp));
scanf("%d %d %d %d %d %d",&L1, &L2, &L3, &C1, &C2, &C3);
scanf("%d",&N);
scanf("%d %d",&start,&end);
int t1=start, t2 = end;
start = min(t1,t2);
end = max(t1,t2);
d[1] = 0;
for(int i = 2; i <= N; i++)
scanf("%d",&d[i]);
//for(int i = start+1; i <= end; i++)
// dp[i] = 0x7F;
for(int i = 1; i <= N; i++) dp[i] = INT_MAX;
dp[start] = 0;
for(int i = start; i <= end; i++)
{
for(int j = start+1; j <= end; j++)
{
int dis = d[j]-d[i];
if(dis<=L1)
{
dp[j] = MIN(dp[j],dp[i]+C1);
}
else if(dis<=L2)
{
dp[j] = MIN(dp[j],dp[i]+C2);
}
else if(dis<=L3)
{
dp[j] = MIN(dp[j],dp[i]+C3);
}
else
{
break;
}
}
}
printf("%d\n",dp[end]);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator