05-07 15:23 已编辑湘潭大学 C++ 发布于湖南

关注

线性dp

1.P1868 饥饿的奶牛

题目描述

有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。

现用汉语翻译为：

有 $N$ 个区间，每个区间 $x,y$ 表示提供的 $x\sim y$ 共 $y-x+1$ 堆优质牧草。你可以选择任意区间但不能有重复的部分。

对于奶牛来说，自然是吃的越多越好，然而奶牛智商有限，现在请你帮助他。

输入格式

第一行一个整数 $N$ 。

接下来 $N$ 行，每行两个数 $x,y$ ，描述一个区间。

输出格式

输出最多能吃到的牧草堆数。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

$1 \leq n \leq 1.5 \times 10^5$ ， $0 \leq x \leq y \leq 3 \times 10^6$ 。

可以尝试线性dp,假设dp[i]表示只选前i个区间的最多吃草数,剩下就要考虑怎么正确的状态转移, f[i]=max(f[i-1],f[j]+a[i].tail-a[i].head+1);//j表示尾小于i且f[j]最大的区间下标,由于f[j]单调不减(求maxf[i-1]),故只要找j最大且r[j]<l[i]即可,每次都找:O(n)状态转移会超时,故考虑二分查找r[j],那么按r排序即可,状态转移O(logn)

2.P1541 [NOIP 2010 提高组] 乌龟棋

题目背景

NOIP2010 提高组 T2

题目描述

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行 $N$ 个格子，每个格子上一个分数（非负整数）。棋盘第 $1$ 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 $M$ 张爬行卡片，分成 $4$ 种不同的类型（ $M$ 张卡片中不一定包含所有 $4$ 种类型的卡片，见样例），每种类型的卡片上分别标有 $1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式

每行中两个数之间用一个空格隔开。

第 $1$ 行 $2$ 个正整数 $N,M$ ，分别表示棋盘格子数和爬行卡片数。

第 $2$ 行 $N$ 个非负整数， $a_1,a_2,…,a_N$ ，其中 $a_i$ 表示棋盘第 $i$ 个格子上的分数。

第 $3$ 行 $M$ 个整数， $b_1,b_2,…,b_M$ ，表示 $M$ 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 $M$ 张爬行卡片。

输出格式

一个整数，表示小明最多能得到的分数。

输入输出样例 #1

输入 #1

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

输出 #1

说明/提示

$1 \le N \le 350,1 \le M \le 120$ ，且 $4$ 种爬行卡片，每种卡片的张数不会超过 $40$ ； $0 \le a_i \le 100(1 \le i \le N),1 \le b_i \le 4(1 \le i\le M)$ 。

一开始我想f[i][][][][]表示到达当前位置用每张卡片[][][][]张的最大分数,一算350*(31**4),会超时.然后发现每张卡片各用多少张就代表了位置,不需要额外状态来表述位置(只用f[c0][c1][c2][c3]).然后,我们可能会疑惑,那卡片的使用顺序怎么办?其实我们不需要看使用顺序,只需要使得score最大的使用顺序即可了,这样就可以不必记录下所有使用顺序的score,我们考虑到底某个位置的最后最后一张牌,到达这个位置获得这个位置的分(无论最后一张用得是什么牌),从而f[c0][c1][c2][c3]=max(f[c0-1][c1][c2][c3],f[c0][c1-1][c2][c3],f[c0][c1][c2-1][c3],f[c0][c1][c2][c3-1])+score[cur_pos],循环顺序只要保证c0,c1,c2,c3从小到大计算(且在这之前遍历所有可能的卡牌使用情况)即可

3.P1002 [NOIP 2002 普及组] 过河卒

题目描述

棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示， $A$ 点 $(0, 0)$ 、 $B$ 点 $(n, m)$ ，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 $B$ 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

输入输出样例 #1

输入 #1

6 6 3 3

输出 #1

说明/提示

对于 $100 \%$ 的数据， $1 \le n, m \le 20$ ， $0 \le$ 马的坐标 $\le 20$ 。

保证起点不是马的控制点。

易错点:这道题不能想当然的把dp[i][0]和dp[0][j]设为1,因为如果这一条线之前有不可通过点,那么这个点也不可到达,应该是dp[0][0]特殊处理,dp[i][0]=dp[i-1][0],dp[0][j]=dp[0][j-1];

4.P2679 [NOIP 2015 提高组] 子串

题目背景

NOIP2015 Day2T2

题目描述

有两个仅包含小写英文字母的字符串 $A$ 和 $B$ 。

现在要从字符串 $A$ 中取出 $k$ 个互不重叠的非空子串，然后把这 $k$ 个子串按照其在字符串 $A$ 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 $B$ 相等？

注意：子串取出的位置不同也认为是不同的方案。

输入格式

第一行是三个正整数 $n,m,k$ ，分别表示字符串 $A$ 的长度，字符串 $B$ 的长度，以及问题描述中所提到的 $k$ ，每两个整数之间用一个空格隔开。

第二行包含一个长度为 $n$ 的字符串，表示字符串 $A$ 。

第三行包含一个长度为 $m$ 的字符串，表示字符串 $B$ 。

输出格式

一个整数，表示所求方案数。

由于答案可能很大，所以这里要求输出答案对 $1000000007(10^9 + 7)$ 取模的结果。

输入输出样例 #1

输入 #1

6 3 1 
aabaab 
aab

输出 #1

输入输出样例 #2

输入 #2

6 3 2 
aabaab 
aab

输出 #2

输入输出样例 #3

输入 #3

6 3 3 
aabaab 
aab

输出 #3

数据范围

对于所有数据： $1\le n\le 1000,1\le m\le 200,1\le k\le m$ 。

计数类问题,考虑dp,线性遍历,考虑如何设计状态和状态转移

思考一下每多一个字符我们可以干什么?要不不管它,要不把它接到前面最后一个串后面,要不从它新开始一个串.再考虑我们如何设计状态使得它无后效性?

1.前面匹配到B的哪个字符串了?不知道的话,那我新的字符都不知道匹配B的哪个位置

2.前面有多少个子串了?不知道的话,怎么能判断子串数量<=k?

3.还需要有一个状态:前面那个字符是不是被计入了?如果前面被计入,这个字符才能接到前面那个串的后面

每次状态转移就只需要这些状态了

u32 dp[205][205][2]{};
    if(a[0]==b[0]) { dp[0][1][1]=1; }
    for(int i=1;i<n;++i)
    {
        u32 ndp[205][205][2]{};
        for(int j=0;j<m;++j)
        {
            for(int j1=1;j1<=k;++j1)
            {
                ndp[j][j1][0]=(dp[j][j1][0]+dp[j][j1][1])%p;//不选a[i]
                if(a[i]==b[j])//可以选a[i]
                {
                    if(j==0)
                    {
                        ndp[j][j1][1]=(j1==1);
                        continue;
                    }//j==0,前面没有匹配的字符,子串长度必须为1
                    ndp[j][j1][1]=(dp[j-1][j1][1]+dp[j-1][j1-1][0]+dp[j-1][j1-1][1])%p;//接在前面,或者再开一个子串
                }
            }
        }
        memcpy(dp,ndp,sizeof(dp));
    }
    cout<<(dp[m-1][k][0]+dp[m-1][k][1])%p;

5.CF1860C Game on Permutation

题目描述

Alice 和 Bob 正在玩一个游戏。他们有一个长度为 $n$ 的排列 $p$ （长度为 $n$ 的排列是一个长度为 $n$ 的数组，其中每个 $1$ 到 $n$ 的元素恰好出现一次）。他们还有一个筹码，可以放在排列的任意一个元素上。

Alice 和 Bob 轮流行动：Alice 先行动，然后 Bob 行动，然后 Alice，再然后 Bob，依此类推。在第一次行动时，Alice 可以选择排列中的任意一个元素，并将筹码放在该元素上。在接下来的每一次行动中，当前玩家必须将筹码移动到同时满足以下两个条件的任意一个元素上：该元素在当前元素的左侧，并且严格小于当前元素（即如果筹码当前在第 $i$ 个元素上，则可以移动到第 $j$ 个元素上，当且仅当 $j < i$ 且 $p_j < p_i$ ）。如果某个玩家无法按照游戏规则移动筹码，则该玩家获胜。