zoj 3627(贪心)-白红宇

zoj 3627(贪心)

阅读量：7078 次

发布时间：2019-06-28

本文共 2014 字，大约阅读时间需要 6 分钟。

思路：半夜了思路有点混乱wa了好几发。一开始坑定两个人距离为m才能获得最大的收益，所以我们就可以枚举单个端点，当距离达到m时在一同一个方向走这是我们只需要算一下剩下几秒，左右两边贪心去最大的即可。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-05-12 23:51 5  * Filename     : poj_1741.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 1000000+10;34 ll num[LEN], sum[LEN];35 int n, p, m, t;36 37 int Min(int a, int b, int c){38 return min(a, min(b, c));39 }40 41 int Max(int a, int b, int c){42 return max(a, max(b, c));43 }44 45 void J(int &pos){46 if(pos == n+1) pos = n;47 else if(pos == 0) pos = 1;48 }49 50 int main()51 {52 // freopen("in.txt", "r", stdin);53 54 while(scanf("%d%d", &n, &p)!=EOF){55 sum[0] = 0;56 for(int i=1; i<=n; i++){57 scanf("%lld", &num[i]);58 sum[i] = sum[i-1] + num[i];59 }60 scanf("%d%d", &m, &t);61 ll ans = 0;62 for(int l=max(1, p-t); l<=p; l++){63 int r = Min(n, l+m, p+t);64 int rest = t - max(p-l, r-p);65 int a = max(1, l-rest);66 int b = min(n, r+rest);67 ans = max(ans, sum[b]-sum[l-1]);68 ans = max(ans, sum[r]-sum[a-1]);69 }70 for(int r=min(n, p+t); r>=p; r--){71 int l = Max(1, r-m, p-t);72 int rest = t - max(p-l, r-p);73 int a = max(1, l-rest);74 int b = min(n, r+rest);75 ans = max(ans, sum[b]-sum[l-1]);76 ans = max(ans, sum[r]-sum[a-1]);77 }78 printf("%lld\n", ans);79 }80 return 0;81 }

View Code

转载于:https://www.cnblogs.com/shu-xiaohao/p/3724657.html

你可能感兴趣的文章