题目考点：dp 题目大意：左下到右上的走法数量，遇到1不走，走到该位置无效（注意快读和取模） 题目分析：过河卒的改版，不过是走的方向变了，思路还是一样的：走到该点的路径条数为左边点条数+下边点的路径条数，状态转移方程：mp[i][j] = mp[i+1][j] + mp[i][j-1] 特判：mp[n][1] = 1，即走到起点的路径数为1 #include<iostream> #include<algorithm> using namespace std; typedef long long LL; const int N = 3010, mod = ...

注意开long long !!!题目考点：dp题目大意：从起点到终点的路径数（多啰嗦一句，分析是dp还是bfs的点就是看求的是最短路径还是路径条数，两种算法解决的问题不同）题目分析：dp[ i ] [ j ] 表示走到（i,j）的路径数，正常情况下dp[i][j]等于上面走下来和左边走过来的路径条数相加，即dp[ i ] [ j ] = dp[ i - 1 ] [ j ] + dp[ i ] [ j - 1 ]遇到马控制的点特判即可 #include<iostream> #include<algorithm> using namespace std; typede...

题目考点：bfs + 优先队列题目概述：每张地图有起点、终点、陷阱、传送门，求最短时间。注意情况有以下几种：起点有陷阱、传送门终点有陷阱、坐传送门还不如走过去时间短等。前两种问题用数组标记即可；第三种情况用优先队列维护，保证不管是坐传送门还是不开启传送门，到达该点的时间是划算的 #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<queue> using namespace std; typedef long long l...

题目考点：线性dp 题目大意：n个小牛♂牛围成一圈传球，问传球m次传回第一个人的情况有几种 题目分析：dp[ i ][ j ] 表示i次传球后，球在第j个人手里的情况，可以想到传球给这个人手里的是他左边的那个人（j-1）或者他右边那个人（j + 1 ）因此dp[ i ][ j ] = dp [ i - 1 ][ j - 1 ] + dp [ i - 1] [ j + 1 ]初始化dp[ 0 ] [ 1 ] = 1表示0次传球传给第一个人的情况只有一种 #include<iostream> #include<algorith> using namespace std...

题目考点：二维线性DP （初学者可以参考代码对样例模拟状态转移的过程，有助于今后理解状态转移） 题目大意：n种花m个花瓶，花瓶顺序以及插入花的顺序固定，每种花在每个花瓶中美观度不同（有负数），问讲n种花插在哪n个花瓶里美观度最大。 题目分析：对于第i种花，它能获得的最大美观度为：在合法区间内，上一种花所在位置后面的花瓶中的最大美观度的位置（其中合法区间是指从上一种花(上一种花用k维护)放的位置开始，到使得i后面的话有花瓶可以放的区间，比如根据题目样例，对于第2种花来说，它最后能放的位置为4，后面至少留1个花瓶的位置）。因此转移方程：dp [ i ][ j ] = max (dp [ i ]...