P3622 [APIO2007]动物园

2021-06-07 11:18

阅读：297

标签：转移 long ++i reg str set eof ace 状态

题目链接

题意分析

这是一道状压\(DP\)的题

一个人只可以欣赏到\(5\)只动物显然可以状压

我们用\(dp[i][j]\)表示当前\([i,i+4]\)中这\(5\)只动物的状态\(j\) 在或者不在

最多可以满意的小朋友数

\(num[i][j]\)表示当前\([i,i+4]\)中这\(5\)只动物的状态\(j\) 在或者不在

可以满意的小朋友数

那么就是

\[dp[i][j]=max(dp[i-1][(j\&15)

其中首先按位与\(15\)是因为

按照关系\(i\)同\(i-1\)个人是共同欣赏\(4\)只动物的

所以我们就提出来

那么前驱状态就只有两种

然后预处理出\(num\)之后正常转移就可以了

同时需要注意的是

由于是一个环

所以最后的状态要等同于开始的状态

所以我们还需要枚举一个状态

CODE:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x7fffffff
#define N 50008
#define IL inline
#define M 10011
#define D 50
#define ull unsigned long long
#define R register
using namespace std;
templateIL void read(T &_)
{
    T __=0,___=1;char ____=getchar();
    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
    while(isdigit(____)) {__=(__

P3622 [APIO2007]动物园

标签：转移 long ++i reg str set eof ace 状态

原文地址：https://www.cnblogs.com/LovToLZX/p/10741477.html

上一篇：Windows运维之道——PXE备份系统

下一篇：开启win10下Ubuntu子系统的SSH服务并设置为开机启动

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：P3622 [APIO2007]动物园
文章链接：http://soscw.com/essay/91718.html

亲，登录后才可以留言！

P3622 [APIO2007]动物园

题目链接

题意分析

CODE:

评论

热门文章

推荐文章

最新文章

置顶文章