状压dp – Tgotp-Blog

5248: [2018多省省队联测]一双木棋

容易写出暴力.
c++代码如下:

上述代码50分.
考虑如何优化
发现其实每一层当前能选的都是固定的.
那么考虑状压来表示出每一层的状态.
因为m最大为10,根据题意显然总变化不会超过10
用1表示向左边移动,0表示该[......]

Read more

NOIP2017 题解

终于开始在晚自习的时候填填noip的坑了。

D1T1传送门

D1T2传送门

D1T3传送门

D2T1传送门

D2T2传送门

D2T3传送门

d1t1:math :

推规律(找规律),a*b-a-b;

c++代码如下:[......]

Read more

1076: [SCOI2008]奖励关

概率dp & 状压dp

从后往前扫。

每一个掉落的概率都是1/n即如果能拿到期望值维f[i][j] = (f[i][j|(1<<z-1)] + a[i])/n

不行得话期望值只用从上一次转移过来,ok。

可以随便套一个滚动数组优化。

c++代码如下:[......]

Read more

tyvj测试

很不爽啊。。。

day1 60 + 100 + 10 = 170

day2 100 + 40 + 80 = 220

总分390

update:然后吐槽一下:tyvj的测评姬大概烂破了天际。。。能测一个小时的代码我还是第一次见。。。莫名其妙的System Error真[......]

Read more

1226 [SDOI2009]学校食堂Dining

状压dp,dp[i][j][k]表示,在i这个人这里,达到了j这个状态,上一个打饭的人是k,然后显而易见可以从i-8 ~ i+7这些点里面来选,然后来判断是否满足。

c++代码如下:

 

E - Compatible Numbers

 

Two integers x and y are compatible, if the result of their bitwise "AND" equals zero, that is, a & b = 0. For example, numbers 90 (10[......]

Read more

送快餐

送快餐
meal.cpp/c/pas
1s / 128M
题目描述 Description
快递员要将n份快餐送到n个不同的地方,编号为1~n,快递员所在的公司编号为0,
现在他从公司出发,要到达这n个地方至少一次,送完后再回到公司,请问最短时间是
多少。现在已知任意两个城市的直接通路的[......]

Read more

杀死机器人

杀死机器人
robot .cpp/c/pas
1s / 128MB
【题目描述】
洛克人又来拯救世界了。他的目的是杀死 Wily 博士做的机器人。在这个任
务里,他将要试着摧毁一些机器人。
一开始,洛克人有一个叫巨型炸弹的武器,可以用来摧毁机器人。不幸的是,
一个武器只能打倒一些特定机[......]

Read more

P1896 [SCOI2005]互不侵犯King

九宫格的话,只要跟上一行对比就好了,用了滚动数组优化,状压dp显而易见,具体看代码注释咯。

NOIP2016T6