7.22集训

Posted on Edited on In

上午

cjh学长讲课了,主要讲的动规 1.线性dp

典型例题

摆花

不会这个题....!!!!!!

王八棋

四个if四个for 注意计数器从0还是1开始的

2.背包（他没讲）

3.区间dp

典型例题

能量项链

石子合并

两个题几乎都一样

给出区间dp的板子:

1
2
3
4
5
6
7
初始化balbalbala.....
for (int len = 2; len <= n; ++ len)
   for (int i = 1; i <= n-len+1; ++ i) {
      int j = i+len-1;
	 for (int k = i; k < j; ++ k)
	    f[i][j] = max/min(f[i][j],f[i][k]+f[k+1][j]*sth..)
	}

其中

f[i][j]=max/min(f[i][j],f[i][k]+f[k+1][j]∗sth..)

4.状压dp

典型例题

奶牛进电梯

学长说题解第一种做法不太好

最好是枚举子集 那样比较好 PS

枚举子集

1
2
3
int S = 233333;
for (int i = S; i; i = (i-1)&S)
   cout <<bitset<10>(i)<<'\n';

还有比较操蛋的插头dp

甩个比较好的链接

插头DP

讲了到题 铺地板

对于此题 我们枚举三个状态，但是这个题有点难，对于我这种初学者不太合适

我们考虑一种简单的题:

还是铺地板，不过没有障碍物，我们铺的都是直线，并且，直线都是长至少为2，宽固定为1

对于这个题 我们规定 能继续延伸无论是横着或者竖着都是1

如果不能继续延伸 规定为0

然后每一行都是2n,有n行，所以复杂度为n∗2n

5.期望dp（他没讲）

6.树形dp（他说是重点）

有上司的舞会

战略游戏

前两个题目都差不多，主要是我们开个f数组，0表示这个点没来（或者是不选），1表示来（或者是选）:f[i][0/1]

然后我们就可以根据他们的儿子来转移

对于上面那道题

f[i][0]=∑max(f[son][0],f[son][1])

f[i][1]=∑f[son][0]+v[i]

其中v[i]表示i这个节点的快乐指数

对于下面那道题

f[i][0]+=f[son][1]

f[i][1]+=min(f[son][0],f[son][1])

树上染色

如图，我们假设节点1的下面有k个黑点，x−−>1这条边为val

我们考虑val对整个图形的影响

设一共有B个黑点，W个白点

顾val对整个图形的影响为：

(k∗(B−k)+(s[1]−k)∗(w−(s[1]−k))∗val

其中s[1]表示以1为祖先的子树的大小(size)

下午

一开始讲了一会，后来就做题了

讲了一个虚树

还有两个动规优化

玩玩具的 玩股票的

对于玩玩具的那个:

  • 1找出dp式子

  • 2魔改

  • 3运用线性规划的知识与凸包的知识

  • 4用斜率优化来做他

对于玩股票的那个:

我们设f[i][j]在第i天有j支股票能获得的最大价值

  • 1 凭空买

f[i][j]=−api∗j 其中(0≤j≤asi)

  • 2 不买也不买

f[i][j]=max(f[i−1][j],f[i][j]

  • 3 在之前的基础上买

f[i][j]=max(f[i][j],f[i−(w+1)][k]−(j−k)∗api

其中(j−asi≤k<j)

  • 4在之前的基础上卖

f[i][j]=max(f[i][j],f[i−(w+1)][k]+(k−j)∗bpi

其中(j<k≤j+bsi)

然后经过一系列nb操作就可以用单调队列来优化了...

但是我既不会写代码也不会写优化

连这些状态都是从题解看过来的

晚上

关于插头dp上午说的那个简单例题，学长给出了代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int64 p = 1e9 + 7;

void work(int n, int m)
{
   unordered_map<int, int64> dp[2];
   int numnow = 0, numnext = 1;
   dp[numnow][0] = 1;
   for(int line = 1; line <= n; ++line)
   {
      for(int i = 1; i <= m; ++i)
      {
         dp[numnext].clear();
         for(auto s = dp[numnow].begin(); s != dp[numnow].end(); ++s)
         {
            int nowst = s->first, nowval = s->second;
            int u = (nowst >> i) & 1, l = (nowst >> (i - 1)) & 1;
            if(u == 0 && l == 0)
            {
               (dp[numnext][nowst ^ (1 << i)] += nowval) %= p;
               (dp[numnext][nowst ^ (1 << (i - 1))] += nowval) %= p;
            }
            if(u == 1 && l == 0)
            {
               (dp[numnext][nowst ^ (1 << i)] += nowval) %= p;
               (dp[numnext][nowst ^ (1 << i) ^ (1 << (i - 1))] += nowval) %= p;
            }
            if(u == 0 && l == 1)
            {
               (dp[numnext][nowst ^ (1 << (i - 1))] += nowval) %= p;
               (dp[numnext][nowst ^ (1 << i) ^ (1 << (i - 1))] += nowval) %= p;
            }
         }
         swap(numnow, numnext);
      }
      dp[numnext].clear();
      for(auto s = dp[numnow].begin(); s != dp[numnow].end(); ++s)
      {
         if(((s->first >> m) & 1) == 0)
            dp[numnext][s->first << 1] = s->second;
      }
      swap(numnow, numnext);
   }
   cout << dp[numnext][0] << endl;
}

int main()
{
   int n, m;
   scanf("%d%d", &n, &m);
   work(n, m);
   return 0;
}

对于这份代码

其中u为up，l为left 分别代表上边和左边来的数字

nowst,nowval分别代表当前这一行的状态，当前及以前已经拥有的方案数

(从左往右更新的,因此i在右边，i−1在左边)

对于特娘的三种if我们来画几个图

对于这个图 我们u和l都为0也就是说，当前状态我们只能再向下或者右转移

上图是nowst^1<<(i−1)的情况 即向下开始直线

向右延伸的直线，即nowst^1<<i

至此u=0,l=0的情况结束。来看u=1,l=0的情况!

当nowst异或两次，即把第i位与第(i−1)位都取反了

对于取反两次的情况，就是顺着原来的方向走，原来是竖着，现在还是竖着

而上图右边的那个情况是 nowst^(1<<i)，即停止下渗

至此u=1,l=0的情况结束。来看u=0,l=1的情况！

当nowst异或两次，即把第i位与第(i−1)位都取反了

对于取反两次的情况，就是顺着原来的方向走，原来是横着着，现在还是横着

而上图右边的那个情况是 nowst^(1<<(i−1)，即停止继续向左

End...