首页 > 代码库 > Easy 2048 Again(状压dp)
Easy 2048 Again(状压dp)
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3802
题意: 从数列A中, 删除若干个数(可以0个), 是删除后的数列, 进行类似 Flappy 2048 游戏的运算, 使结果最大, 求该最大值。
题解: 每个数ai, 取或不取, 满足 可用二进制表示。 当 ai < a[i + 1] 是, 易想到 如果两个数都取, ai 将不会在合并。 所以只需考虑ai[i + 1] 前的 降序列即可 .如果没个数都为16, 合并后的数列的最大值为4026 = 2^12。 也就是说, a[i + 1]最多只需考虑 合并到a[i +1]为后的前 12项。
具体的看 代码吧
1 /***Good Luck***/ 2 #define _CRT_SECURE_NO_WARNINGS 3 #include <iostream> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <stack>10 #include <map>11 #include <queue>12 #include <vector>13 #include <set>14 #include <functional>15 #include <cmath>16 17 #define Zero(a) memset(a, 0, sizeof(a))18 #define Neg(a) memset(a, -1, sizeof(a))19 #define All(a) a.begin(), a.end()20 #define PB push_back21 #define inf 0x3f3f3f3f22 #define inf2 0x7fffffffffffffff23 #define ll long long24 using namespace std;25 //#pragma comment(linker, "/STACK:102400000,102400000")26 27 const int mw = 1 << 13;28 int n;29 int arr[mw]; // 滚动数组30 int mx;31 inline int add(int i, int v) {32 int tmp = ((i + v) | i) - i ; 33 int ans = v;34 while (v < tmp) {35 ans = ans + (v <<= 1);36 }37 return ans;38 }39 void cal(int v) {40 int tmpv;41 int tmpmx = 0;42 for (int i = mx; i >= 0; --i) { //mx 记录每次cal 时, 改动的最大值。 (不知为什么, 没优化这一步, 超时, 优化后 10ms,相差好大)43 if ((i & (v - 1))) { 44 tmpmx = max(tmpmx, arr[i]); // 记录 arr[i + 1] > arr[i]中的多种情况 下的最大得分。45 continue;46 }47 if (arr[i] && arr[i + v] < arr[i] + (tmpv = add(i,v))) { // 计算并更新arr[i + 1] <= arr[i]中多种情况48 arr[i + v] = arr[i] + tmpv;49 mx = max(i + v, mx); // 记录该次运行时所用的最大 数。50 }51 }52 arr[v] = v + tmpmx;53 mx = max(v, mx);54 }55 56 int main() {57 int T;58 scanf("%d", &T);59 while (T--) {60 Zero(arr);61 int val = 0;62 scanf("%d", &n);63 scanf("%d", &val);64 mx = val; //第一次的范围65 cal(val);66 for (int i = 2; i <= n; ++i) {67 scanf("%d", &val);68 cal(val);69 }70 int ans = 0;71 for (int i = 0; i < mw; ++i) ans = max(ans, arr[i]);72 printf("%d\n", ans);73 }74 return 0;75 }
Easy 2048 Again(状压dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。