首页 > 代码库 > zoj 3627#模拟#枚举
zoj 3627#模拟#枚举
There are n cities(1, 2, ... ,n) forming a line on the wonderland. city i and city i+1 are adjacent and their distance is 1. Each city has many gold coins. Now, Alice and her friend Bob make a team to go treasure hunting. They starts at city p, and they want to get as many gold coins as possible in T days. Each day Alice and Bob can move to adjacent city or just stay at the place, and their action is independent. While as a team, their max distance can‘t exceed M.
Input
The input contains multiple cases. The first line of each case are two integers n, p as above. The following line contain n interger,"v1 v2 ... vn" indicate the gold coins in city i. The next line is M, T. (1<=n<=100000, 1<=p<=n, 0<=vi<=100000, 0<=M<=100000, 0<=T<=100000)
Output
Output the how many gold coins they can collect at most.
Sample Input
6 31 2 3 3 5 42 1
Sample Output
8
Hint
At day 1: Alice move to city 2, Bob move to city 4.
They can always get the gold coins of the starting city, even if T=0
Author: LI, Chao Contest: ZOJ Monthly, July 2012
题意 转自：http://blog.csdn.net/cscj2010/article/details/7819110
题意:n个城市排成一行，每个城市中有vi个金币。两个人同时从同一个个城市出发，单位时间能走到相邻城市。
- 到达城市获取金币不耗时间，且任意时刻两人距离不可以超过m，问t个时间他们最多能获得多少金币。
- 如果 m >= t * 2,两个人两个方向一直走
- 否则 两人一直向两边走指导相距m，注意，若m为奇数，则某人要停走一天。
- 然后维持距离同时向左向右枚举剩余天数
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 #include<vector> 10 11 #define N 100005 12 #define M 15 13 #define mod 1000000007 14 #define mod2 100000000 15 #define ll long long 16 #define maxi(a,b) (a)>(b)? (a) : (b) 17 #define mini(a,b) (a)<(b)? (a) : (b) 18 19 using namespace std; 20 21 int n,p; 22 ll v[N]; 23 ll tot; 24 ll sum[N]; 25 int m,t; 26 int t1,t2; 27 28 void ini() 29 { 30 int i; 31 tot=0; 32 memset(sum,0,sizeof(sum)); 33 for(i=1;i<=n;i++){ 34 //scanf("%lld",&v[i]); 35 cin>>v[i]; 36 sum[i]=sum[i-1]+v[i]; 37 } 38 scanf("%d%d",&m,&t); 39 } 40 41 void solve() 42 { 43 int i,j,o; 44 if(m/2>=t) 45 { 46 i=max(1,p-t); 47 j=min(n,p+t); 48 tot=sum[j]-sum[i-1]; 49 return ; 50 } 51 t1=min(t,m/2); 52 t2=t-t1; 53 i=max(1,p-t); 54 j=min(n,p+t1); 55 tot=sum[j]-sum[i-1]; 56 for(o=0;o<=t2;o++){ 57 i=max(1,p-t1-o); 58 if(m%2==1 && o!=0){ 59 j=max(p+t1,p+t1+t2-2*o+1); 60 j=min(n,j); 61 } 62 63 else{ 64 j=max(p+t1,p+t1+t2-2*o); 65 j=min(n,j); 66 } 67 tot=max(tot,sum[j]-sum[i-1]); 68 } 69 70 j=min(n,p+t); 71 i=max(1,p-t1); 72 tot=max(tot,sum[j]-sum[i-1]); 73 for(o=0;o<=t2;o++){ 74 if(m%2==1 && o!=0){ 75 i=min(p-t1,p-t1-t2+2*o-1); 76 i=max(1,i); 77 } 78 79 else{ 80 i=min(p-t1,p-t1-t2+2*o); 81 i=max(1,i); 82 } 83 84 j=min(n,p+t1+o); 85 // printf(" o=%d i=%d j=%d sum=%I64d\n",o,i,j,sum[j]-sum[i-1]); 86 tot=max(tot,sum[j]-sum[i-1]); 87 } 88 //tot=v[p]; 89 // i=max(p-t,1); 90 //if(i==1){ 91 // tot=sum[] 92 // } 93 // j=min(p+1,n); 94 95 } 96 97 int main() 98 { 99 //freopen("data.in","r",stdin);100 // scanf("%d",&T);101 // for(int cnt=1;cnt<=T;cnt++)102 // while(T--)103 while(scanf("%d%d",&n,&p)!=EOF)104 {105 //if(g==0 && b==0 &&s==0) break;106 ini();107 solve();108 //printf("%lld\n",tot);109 cout<<tot<<endl;110 }111 112 return 0;113 }
zoj 3627#模拟#枚举