zoj 3627#模拟#枚举

Treasure Hunt II

Time Limit: 2 Seconds Memory Limit: 65536 KB

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,"v₁ v₂ ... v_n" indicate the gold coins in city i. The next line is M, T. (1<=n<=100000, 1<=p<=n, 0<=v_i<=100000, 0<=M<=100000, 0<=T<=100000)

Output

Output the how many gold coins they can collect at most.

Sample Input

6 3

1 2 3 3 5 4

2 1

Sample Output

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为奇数，则某人要停走一天。
然后维持距离同时向左向右枚举剩余天数

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<map>

 #include<vector>

 #define N 100005

 #define M 15

 #define mod 1000000007

 #define mod2 100000000

 #define ll long long

 #define maxi(a,b) (a)>(b)? (a) : (b)

 #define mini(a,b) (a)<(b)? (a) : (b)

 using namespace std;

 int n,p;

 ll v[N];

 ll tot;

 ll sum[N];

 int m,t;

 int t1,t2;

 void ini()

 {

    int i;

    tot=;

    memset(sum,,sizeof(sum));

    for(i=;i<=n;i++){

         //scanf("%lld",&v[i]);

         cin>>v[i];

         sum[i]=sum[i-]+v[i];

    }

    scanf("%d%d",&m,&t);

 }

 void solve()

 {

     int i,j,o;

     if(m/>=t)

     {

         i=max(,p-t);

         j=min(n,p+t);

         tot=sum[j]-sum[i-];

         return ;

     }

     t1=min(t,m/);

     t2=t-t1;

     i=max(,p-t);

     j=min(n,p+t1);

     tot=sum[j]-sum[i-];

     for(o=;o<=t2;o++){

         i=max(,p-t1-o);

         if(m%== && o!=){

             j=max(p+t1,p+t1+t2-*o+);

             j=min(n,j);

         }

         else{

             j=max(p+t1,p+t1+t2-*o);

             j=min(n,j);

         }

         tot=max(tot,sum[j]-sum[i-]);

     }

     j=min(n,p+t);

     i=max(,p-t1);

     tot=max(tot,sum[j]-sum[i-]);

     for(o=;o<=t2;o++){

         if(m%== && o!=){

             i=min(p-t1,p-t1-t2+*o-);

             i=max(,i);

         }

         else{

             i=min(p-t1,p-t1-t2+*o);

             i=max(,i);

         }

         j=min(n,p+t1+o);

        // printf(" o=%d i=%d j=%d sum=%I64d\n",o,i,j,sum[j]-sum[i-1]);

         tot=max(tot,sum[j]-sum[i-]);

     }

     //tot=v[p];

    // i=max(p-t,1);

     //if(i==1){

    //     tot=sum[]

    // }

    // j=min(p+1,n);

 }

 int main()

 {

     //freopen("data.in","r",stdin);

    // scanf("%d",&T);

    // for(int cnt=1;cnt<=T;cnt++)

    // while(T--)

     while(scanf("%d%d",&n,&p)!=EOF)

     {

         //if(g==0 && b==0 &&s==0) break;

         ini();

         solve();

         //printf("%lld\n",tot);

         cout<<tot<<endl;

     }

     return ;

 }

巴特西