Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:为啥DP要1100多ms?O(N)啊,顺带送一个测试数据

Posted by 20110531 at 2011-11-13 12:26:25 on Problem 3377
In Reply To:为啥DP要1100多ms?O(N)啊,顺带送一个测试数据 Posted by:temp_ptr at 2011-10-28 02:57:00
#include<iostream>
#include<cstdio>
#define x 1000010
#define mmin(m,n) m<n?m:n
using namespace std;
int a[x];//北岸 各段时间 
int b[x];//南岸 各段时间 
int c[x];//过河 各段时间 
__int64 dpa,dpb;// dpa 终点在北岸所用时间,dpb 终点在南岸所用时间 
int N;
int start,end;// 起点,终点 
bool flaga,flagb;// 在河哪岸的标志 
void dp()
{
   int i;
   __int64 temp;
   for(i=start+1;i<=end;++i)
   {
       temp=dpa;
       dpa=mmin(dpa+a[i],dpb+b[i]+c[i]);
       dpb=mmin(dpb+b[i],temp+a[i]+c[i]);
   }
   if(flagb)printf("%d\n",dpb);
   else printf("%d\n",dpa);
}
int main()
{
   int i;
   while(scanf("%d",&N)&&N)
   {
   scanf("%d %d %d %d",&flaga,&start,&flagb,&end);
   if(start>end)
   {
      start=start^end;
      end=start^end;
      start=start^end;
      
      flaga=flaga^flagb;
      flagb=flaga^flagb;
      flaga=flaga^flagb;
   }
   for(i=1;i<=N;++i)
   scanf("%d",&a[i]);
   for(i=0;i!=N+1;++i)
   scanf("%d",&c[i]);
   for(i=1;i<=N;++i)
   scanf("%d",&b[i]);
   if(!flaga)
   {
     dpa=0;
     dpb=c[start];
   }
   else
   {
       dpa=c[start];
       dpb=0;
   }
   dp();
   }
   system("pause");
   return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator