Main » 2013 August 20 » 提高组模拟赛
10:18 AM 提高组模拟赛 |
PROB. 拍照(photo.pas/c/cpp, 2s, 512MB) 【题目描述】 fsygd来到了noi赛场上，看到了n个神牛分布在一条直线上。fsygd把这条直线分成了1
000 000 000个格子，每个神牛都位于其中一个格子。fsygd很想把神牛们的风采全部拍下来，但由于他的相机配置太差，拍摄遇到了困难。 fsygd有两个相机，功率分别为3.5W和7.0W。由于存储卡的限制，3.5W的相机只能拍摄P次，7.0W的相机只能拍摄Q次。3.5W的相机一次可以拍摄连续L个格子，而7.0W的相机一次可以拍摄连续
【输入格式】 第一行三个整数n, P, Q。 第i (2<=i<=n+1) 行一个整数Ai，表示第i个神牛的位置。
【输出格式】 一个整数，表示L的最小值。
【样例输入1】 3 1 1 2 11 17
【样例输出1】 4
【样例输入2】 13 3 2 33 66 99 10 83 68 19 83 93 53 15 66 75
【样例输出2】 9
【样例解释】 样例1的一种方案是：使用3.5W相机拍摄1~4格，使用7.0W相机拍摄10~17格。
【数据规模】 50%的数据，n <=
100； 100%的数据，1 <=
n <= 2000，1 <= P, Q, Ai <= 1,000,000,000。 #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #define N 4010 using namespace std; int n,m,i,j,f[N][N],next1[N],next2[N],a[N]; int max(int a,int b) { if (a>b) return a; return b; } int check(int P,int Q,int L) { int i,j; memset(f,0xff,sizeof(f)); memset(next1,0,sizeof(next1)); memset(next2,0,sizeof(next2)); for (i=1;i<=n-1;i++) for (j=i+1;j<=n;j++) if (a[j]-a[i]+1<=L) next1[i]=max(next1[i],j); for (i=1;i<=n-1;i++) for (j=i+1;j<=n;j++) if (a[j]-a[i]+1<=2*L) next2[i]=max(next2[i],j); for (i=1;i<=n;i++) { if (next1[i]==0) next1[i]=i; if (next2[i]==0) next2[i]=i; } f[1][0]=next1[1];f[0][1]=next2[1]; for (i=0;i<=P;i++) for (j=0;j<=Q;j++) { f[i+1][j]=max(f[i+1][j],next1[f[i][j]+1]); f[i][j+1]=max(f[i][j+1],next2[f[i][j]+1]); if (f[i][j]==n) return 1; } return 0; } int main() { freopen("photo.in","r",stdin); freopen("photo.out","w",stdout); int p,q,l; scanf("%d %d %d",&n,&p,&q); int m=0; for (i=1;i<=n;i++) { scanf("%d",&a[i]); if (a[i]>m) m=a[i]; } sort(a+1,a+1+n); int L=1,R=m; while (1) { int mid=(L+R)>>1; if (R-L==1) { if (check(p,q,L)) {printf("%d\n",L);return 0;} else {printf("%d\n",R);return 0;} } if (check(p,q,mid)) R=mid;else L=mid; } } |
|
|
| Total comments: 0 | |