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:在下来回馈社会了!!数据和参考程序!!

Posted by sun199 at 2013-03-14 19:13:59 on Problem 1925
In Reply To:在下来回馈社会了!!数据和参考程序!! Posted by:talenth1 at 2010-12-11 17:22:06
> 数据地址:http://acm.pku.edu.cn/pku2004/data/Preliminary.zip
> 下载页面:http://acm.pku.edu.cn/pku2004/ques.htm 选网络预赛
> 
> 我的dp程序:
> /*
> ID:   talenth1
> PROG: p1925
> LANG: C++
> */
> #include<iostream>
> #include<cstdlib>
> #include<cstring>
> #include<cmath>
> #define maxn 5001
> #define maxd 3000010
> #define oo 16843009
> using namespace std;
> struct Node{
>     int p,d;
>     };
> int t,n,h,edge,x[maxn],y[maxn],f[maxd];
> Node que[maxd];
> void datain()
> {
>     scanf("%d",&n);
>     edge=0;
>     for(int i=1;i<=n;i++){
>         scanf("%d%d",&x[i],&y[i]);
>         edge=max(edge,1+x[i]+(int)sqrt(1.0*y[1]*(2*y[i]-y[1])));
>         }
>     h=y[1];
> }
> void work()
> {
>     __int64 dx,dy;
> 	int ans=oo;
>     bool signal=false;
>     memset(f,1,sizeof(f));
>     f[x[1]]=0;
>     for(int i=2;i<=n;i++){
>         for(int k=x[i];k<=edge;k++){
>             dx=k-x[i];
>             dy=h-y[i];
>             if(dx*dx+dy*dy>(__int64)y[i]*y[i])break;
>             if(2*x[i]-k>=x[1])
> 				f[k]=min(f[k],f[2*x[i]-k]+1);
> 			else break;
>             if(k>=x[n]&&f[k]<ans){
> 				ans=f[k];
> 				signal=true;
> 				}
>             }
>         }
> 	if(signal)printf("%d\n",ans);
> 	else printf("-1\n");  
> }
> int main()
> {      
>     scanf("%d",&t);
>     for(int i=1;i<=t;i++){
>         datain();
>         work();
>         }
>     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