51nod 1380:夹克老爷的逢三抽一
第一行1个整数N(3<=N<=10^5-1,N%3==0) 第2-N+1行:每行1个数对应村民i手中的铜钱。(0<=m[i]<=10^9)
一个整数,说明在夹克老爷的收钱规则下你最多能够为夹克老爷搜刮到多少铜钱
6 6 2 3 4 5 9
13
问题等价于N长的数组中抽取N/3个不相邻的值使得和最大(首尾也不能同时取)
#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <queue> #pragma warning(disable:4996) using namespace std; #define impossible -1*(1e9+7) struct no { long long val; int pos; friend bool operator<(no n1, no n2) { return n1.val < n2.val; } }node[100005]; int n; long long val[100005]; int main() { //freopen("i.txt", "r", stdin); //freopen("o.txt", "w", stdout); int i, k, temp, out; unsigned long long sum; no n_temp; priority_queue<no>q; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &temp); node[i].val = temp; node[i].pos = i; q.push(node[i]); val[i] = temp; } k = 0; sum = 0; out = n / 3; while (true) { n_temp = q.top(); if (n_temp.val <= 0) break; if (val[n_temp.pos] != impossible) { q.pop(); sum += n_temp.val; int le = n_temp.pos; int ri = n_temp.pos; while (val[(le - 1 + n) % n] == impossible) { le--; } while (val[(ri + 1 + n) % n] == impossible) { ri++; } no nn_temp; nn_temp.val = val[(le - 1 + n) % n] + val[(ri + 1 + n) % n ] - n_temp.val; nn_temp.pos = n_temp.pos; q.push(nn_temp); val[n_temp.pos] = nn_temp.val; val[(le - 1 + n) % n] = impossible; val[(ri + 1 + n) % n] = impossible; k++; } else { q.pop(); } if (k == out) break; } printf("%lld\n", sum); //system("pause"); return 0; }