APIO2007-动物园

下个月就是APIO了，07年的题都不会，准备打铁了，在此ORZ Qiuly。

首先我们发现这题并不好搞，无论什么方法总有一点问题，它过不去（复杂度裂了，后效性处理不了····），然而这就是APIO的毒瘤之处了，读题你就得读个7~8 mins，然后瓜起。

好了，不说废话。

Solution

通读题面多次，此题一个特别牛逼的地方在于一个人他是否高兴相关的点特别少（5个），且连续，题目还好心的告诉你每个人可视点单增，这足以说明一些问题（然而蒻如我并没有看出来），这道题可能可以动规。

考虑如何动规，我们尝试将状态每5个一组存下来，记起点为st，设数组num[st][S]强制定义为起点为st，st,st+1,st+2,st+3,st+4状态为S的贡献。

然后转移方程就显然了： f[i][S]=max(f[i-1][(S&15)<<1],f[i-1][(S & 15) << 1 | 1]) + num[i][S]。

就结束了。

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') {if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c= getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void write(T res)
{
    if(res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
const int N = 1e4 + 5, M = 5e4 + 5, mod = 998244353;
int n, c;
int num[M][32]; // 从i位开始往后数4位的状态此时小朋友开心的个数
inline void init()
{
    for(int i = 1, fear, like, st, lk, dk;i <= c;i ++)
    {
        fear = like = 0;
        read(st, dk, lk);
        for(int j = 1, a;j <= dk;j ++)
            read(a), a = (a - st + n) % n, fear |= 1 << a;
        for(int j = 1, a;j <= lk;j ++)
            read(a), a = (a - st + n) % n, like |= 1 << a;
        for(int j = 0;j <= 31;j ++)
            if(((fear & j) < fear) || ((like & j) != 0)) num[st][j] ++;
    }
}
int f[M][32], ans;
int main()
{
    read(n, c);
    init();
    for(int i = 0;i < 32;i ++)
    {
        memset(f[0], 128, sizeof(f[0]));
        f[0][i] = 0;
        for(int j = 1;j <= n;j ++)
            for(int k = 0;k < 32;k ++)
                f[j][k] = max(f[j - 1][(k & 15) << 1], f[j - 1][(k & 15) << 1 | 1]) + num[j][k];
        ans = max(ans, f[n][i]);
    }
    write(ans);
    return 0;
}