首页 > 代码库 > zoj 3627(贪心)

zoj 3627(贪心)

2024-07-04 05:48:11   226人阅读

思路：半夜了思路有点混乱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 <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
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<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> 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

 


联系
我们