洛谷2672(接頭辞とテクニック)

9632 ワード

参照問題解
テーマの本質:最良の決定は必ず2種類しかありません:前Xの大きいA値、前X-1の大きいA値に1つのA+2*Sを加えて最大です.
解決方法:
Aの大きい順から小さい順に並べ替えます.
メンテナンス:1.Aの接頭辞と;2.前のi個の中で一番大きいS;3.i以降最大のA+2*S.
そしてO(n)maxを一度でいいです.

 1 #pragma comment(linker, "/STACK:1024000000,1024000000")
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include <string>
13 #include 
14 #include 
15 #include 
16 #include <set>
17 #include 
18 #include 
19 #include 
20 #include 
21 #define ri readint()
22 #define gc getchar()
23 #define R(x) scanf("%d", &x)
24 #define W(x) printf("%d
", x)
25 #define init(a, b) memset(a, b, sizeof(a))
26 #define rep(i, a, b) for (int i = a; i <= b; i++)
27 #define irep(i, a, b) for (int i = a; i >= b; i--)
28 #define ls p << 1
29 #define rs p << 1 | 1
30 using namespace std;
31 
32 typedef double db;
33 typedef long long ll;
34 typedef unsigned long long ull;
35 typedef pair<int, int> P;
36 const int inf = 0x3f3f3f3f;
37 const ll INF = 1e18;
38 
39 inline int readint() {
40     int x = 0, s = 1, c = gc;
41     while (c <= 32)    c = gc;
42     if (c == '-')    s = -1, c = gc;
43     for (; isdigit(c); c = gc)
44         x = x * 10 + c - 48;
45     return x * s;
46 }
47 
48 const int maxn = 1e5 + 5;
49 struct family {
50     int s, a;
51 
52     family() {
53         s = a = inf;
54     }
55 
56     bool operator < (const family b) const {
57         return a > b.a;
58     }
59 };
60 
61 int main() {
62     int n = ri;
63     vector v(n + 1);
64     rep(i, 1, n)    v[i].s = ri;
65     rep(i, 1, n)    v[i].a = ri;
66     sort(v.begin(), v.end());
67 
68     int maxpres[n+1], suma[n+1], maxsufall[n+2];
69     init(maxpres, 0), init(suma, 0), init(maxsufall, 0);
70     rep(i, 1, n)    maxpres[i] = max(maxpres[i - 1], v[i].s);
71     rep(i, 1, n)    suma[i] = suma[i - 1] + v[i].a;
72     irep(i, n, 1)    maxsufall[i] = max(maxsufall[i + 1], v[i].a + v[i].s * 2);
73 
74     vector<int> ans;
75     rep(i, 1, n)    ans.push_back(max(suma[i] + 2 * maxpres[i], suma[i - 1] + maxsufall[i]));
76     for (int i : ans)    W(i);
77     return 0;
78 }

転載先:https://www.cnblogs.com/AlphaWA/p/10434406.html

Python入門(七)dict

Android開発FAQの詳細