美团第四题，优惠券合并
场景
input：
output：
样例：
代码：
测试结果：
第四题：
场景
小明有一堆不面额的代金券，顺序打乱，例如2,1,1，2，1，如果相邻两个代金券相同，可以进行一次合并，2,2,2,1，合并一次可以得到一张无限期使用的1元券，求小明最多可以得到多少无限期的1元卷。
input：
第一行输入N（2≤N≤500），表示代金券的个数，第二行输入N个数，分别表示代金券的面额x(1xi≤1000)。
output：
输出一个整数,表示获得的代金券的个数。
样例：
input：
5
2 1 1 2 1
output：
2
结果解释：2 2 2 1，4 2 1，无法合并合并两次
测试用例
5
1 1 2 1 1
3
10
1 1 1 1 4 4 2 2 2 2
8
19
6 3 3 3 3 3 12 20 5 5 5 5 5 10 2 2 4 4 8
11
500
1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7
1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7
1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7
1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7
1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7 1 2 3 4 4 5 5 6 6 7
150
500
91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99
91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99
91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99
91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99
91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99 91 92 93 94 94 96 97 98 99
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
50
#include <iostream>
#include<string>
#include<algorithm>
#include<time.h>
#include<list>
#include<functional>
#include<numeric>
#include<queue>
#include<utility>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>
#include <climits>
#define pow(x,y) int(pow(x,y))
int main() {
int n;
while (cin >> n) {
vector<int> v;
// srand(n);
int sum=0;
for (int i = 0; i < n; i++) {
int m;
cin >> m;
sum += m;
v.push_back(m);
}
// }
vector<vector<pair<int, int>>> vv(n, vector<pair<int, int>>(50001, { 0,0 }));
vv[0][v[0]] = { 1,0 };
/* for (int i = 1; i < n; i++) {
vv[i][v[i]].first = 1;
//if (i - vv[i][v[i]].first >= 0) {
for (int k = v[i] + 1; k <= 110; k++) {
if (i - vv[i][k - 1].first >= 0 && vv[i - vv[i][k - 1].first][k - 1].first != 0) {
vv[i][k].first = vv[i - vv[i][k - 1].first][k - 1].first + vv[i][k - 1].first;
vv[i][k].second = vv[i - vv[i][k - 1].first][k - 1].second + vv[i][k - 1].second + 1;
}
else break;
}
// }
}*/
for (int i = 1; i < n; i++) {
vv[i][v[i]].first = 1;
//if (i - vv[i][v[i]].first >= 0) {
for (int k = 1; k <= 9; k++) {
if (i - vv[i][int(pow(2,k - 1)*v[i])].first >= 0 && vv[i - vv[i][pow(2, k - 1) * v[i]].first][pow(2, k - 1) * v[i]].first != 0) {
vv[i][int(pow(2, k)) * v[i]].first = vv[i - vv[i][pow(2, k - 1) * v[i]].first][pow(2, k - 1) * v[i]].first + vv[i][pow(2, k - 1) * v[i]].first;
vv[i][int(pow(2, k) * v[i])].second = vv[i - vv[i][pow(2, k - 1) * v[i]].first][pow(2, k - 1) * v[i]].second + vv[i][pow(2, k - 1) * v[i]].second + 1;
}
else break;
}
// }
}
vector<vector<int>> re(n, vector<int>(50001, 0));
//int re[501][50000];
re[0][v[0]] = 1;
for (int i = 1; i < n-1; i++) {
re[i][0] = re[i - 1][v[i]];
for (int ii = 0; ii <= 8; ii++) {
if (i - vv[i][v[i+1]*pow(2,ii)].first >= 0 && vv[i][v[i + 1] * pow(2, ii)].first != 0)
re[i][v[i + 1] * pow(2, ii)] = max(re[i][0], re[i - vv[i][v[i + 1] * pow(2, ii)].first][v[i + 1] * pow(2, ii)*2] + 1 + vv[i][v[i + 1] * pow(2, ii)].second);
else if (i - vv[i][v[i + 1] * pow(2, ii)].first < 0 && vv[i][v[i + 1] * pow(2, ii)].first != 0) {
re[i][v[i + 1] * pow(2, ii)] = max(re[i][0], vv[i][v[i + 1] * pow(2, ii)].second + 1);
}
else
re[i][v[i + 1] * pow(2, ii)] = re[i][0];
}
//re[i][] = max(re[i][0], re[i - vv[i][].first][] + vv[i][].second);
}
//for (auto s : v) {
// cout << s << ' ';
// }
cout << endl<< re[n-2][v[n-1]] << endl;
system("pause");
}
}
国家电网工作强度 101人发布
