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

在下来回馈社会了！！数据和参考程序！！

Posted by talenth1 at 2010-12-11 17:22:06 on Problem 1925 
数据地址：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