2015 NEERC Moscow - H - Hashing

Posted on By 二价氢

试题链接:H. Hashing

题意,在序列中挑选一个子序列,使得最大,序列长度不超过,元素大小不超过0xFF

显然,我们有如下做法

其中,i为处理的第i个数,j为这是选择的第几个数

然而,我们注意到,这个算法的时间复杂度是的,不足以完成此题

但是,注意到一旦我们确定了选择多少个数,那么答案可以拆为

即,答案大小不与i的其它位数相关,因而,我们可以直接用i二进制表示的后8位来表示状态,这样状态数就剪刀了,是可以接受的复杂度

同时额外记下前面已经选择了多少个数即可

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <utility>
using namespace std;
const int maxn = 100000 + 5;
typedef pair<long long, int> pli;
pli ans[256][maxn];
int n, aa;
char ai[3];
int main()
{
    scanf("%d", &n);
    ans[0][0] = pli(0, -1);
    for (int i = 1; i < 256; i++) ans[i][0] = pli(0x8000000000000000ll, -1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", ai);
        sscanf(ai, "%X", &aa);
        for (int j = 0; j < 256; j++)
        {
            pli &lst = ans[j][i - 1];
            pli &llt = ans[(j + 255) & 255][i - 1];
            ans[j][i] = max(lst, pli(llt.first + (aa ^ (llt.second + 1)), llt.second + 1));
        }
    }
    long long aans = 0;
    for (int j = 0; j < 256; j++)
        aans = max(aans, ans[j][n].first);
    cout << aans << endl;
    return 0;
}