bzoj|[bzoj 1226--SDOI2009]学校食堂Dining
小F的学校在城市的一个偏僻角落,所有学生都只好在学校吃饭。学校有一个食堂,虽然简陋,但食堂大厨总能做出让同学们满意的菜肴。当然,不同的人口味也不一定相同,但每个人的口味都可以用一个非负整数表示。由于人手不够,食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的,若前一道菜的对应的口味是a,这一道为b,则做这道菜所需的时间为(aor b)-(a and b),而做第一道菜是不需要计算时间的。其中,or 和and表示整数逐位或运算及逐位与运算,C语言中对应的运算符为“|”和“&”。学生数目相对于这个学校还是比较多的,吃饭做菜往往就会花去不少时间。因此,学校食堂偶尔会不按照大家的排队顺序做菜,以缩短总的进餐时间。虽然同学们能够理解学校食堂的这种做法,不过每个同学还是有一定容忍度的。也就是说,队伍中的第i个同学,最多允许紧跟他身后的Bi个人先拿到饭菜。一旦在此之后的任意同学比当前同学先拿到饭,当前同学将会十分愤怒。因此,食堂做菜还得照顾到同学们的情绪。现在,小F想知道在满足所有人的容忍度这一前提下,自己的学校食堂做完这些菜最少需要多少时间。【bzoj|[bzoj 1226--SDOI2009]学校食堂Dining】这道题dp很显然,但是怎么设计状态呢?我们可以发现最多把8个数分成一个部分,这个部分里的数可以不按顺序摆放,前面的数只需记录最后一个拿到饭的同学的编号就可以计算了,而那个编号也有一定的限制。
那f[i][j][k],表示1~i-1已经被摆放,j表示i ~i+7的是否摆放,k前一个摆放的编号(只可能是i-8 ~i+7,自己想一下),dp方程就可以推了,那这道题就做完了。
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void pr1(int x){write(x),putchar(' ');
}
inline void pr2(int x){write(x),puts("");
}
int w[1010],p[1010],f[1010][550][20];
int main()
{
//freopen("1226.in","r",stdin);
//freopen("1226.out","w",stdout);
int T=read();
while(T--)
{
int n=read();
for(int i=1;
i<=n;
i++)w[i]=read(),p[i]=read();
memset(f,63,sizeof(f));
f[1][0][7]=0;
for(int i=1;
i<=n;
i++)
{
for(int j=0;
j<(1<<8);
j++)
{
for(int k=0;
k<=15;
k++)
{
if(f[i][j][k]==f[0][0][0])continue;
if(j&1)f[i+1][j>>1][k-1]=min(f[i+1][j>>1][k-1],f[i][j][k]);
else
{
int mn=inf;
for(int d=0;
d<8;
d++)
{
if((j>>d)&1)continue;
if(i+d>mn)break;
mn=min(mn,i+d+p[i+d]);
int wy=w[i+k-8]^w[i+d];
if(i+k<=8)wy=0;
f[i][j+(1<
推荐阅读
- 学校门口
- “寓教于乐,丰知润德”——沭东实验学校临沂龙园研学旅行企划书
- 《教育心理学》读书笔记十四---学校班级管理的现状分析与策略研究
- 排名榜之化妆学校
- 你的大学校园景色是怎样的呢?
- 忆非忆
- 武威市电视台对黄羊镇九年制学校进行采访
- 惊艳
- 突袭
- 记一次有意义的研学|记一次有意义的研学 - 草稿 - 草稿