#动态规划 #多次dp 题意  有n块木板，每块木板有m格，你可以粉刷t次，每次可以粉刷连续的若干格，不能覆盖 给定正确的粉刷方案，请问最多可以刷对多少格 0<=n,m<=50,t<=2500  思路  如果只有一块木板，可以线性dp解决 表示刷i次，刷到j  对于若干块板子，如果能在O(1)的时间知道对于任意一块板子刷到某一个程度的正确格数就可以dp 预处理每一块木板的价值 再dp任意块的价值 注意考虑每个循环的意义确定范围  代码 #include<bits/stdc++.h> #define int long long using namespace std...

#妙妙题 #动态规划 题意  倒置金字塔形的砖块墙，共有n行，第i行有n-i+1块砖 每块砖有价值，敲掉一块砖需要敲掉它左上和右上的两块砖 敲掉m块砖能获得的最大价值总和是多少 n<=50,m<=500  思路  原数据读入形式如下  1 2 3 4 5 1 2 3 4 1 2 3 1 2 1   第一想法状压dp，每行状态二进制表示，但是n在50左右，二进制不够表示，状压寄 换一种表示形式  1 2 3 4 5 1 2 3 4 1 2 3 1 2 1   把原来的一斜列视为一列，原来的左上和右上变为正上和右上 对于敲除一块砖，他上面的所有砖必然敲除 同时对于他的下一列，最多只能敲...

题意  有k个物品，每个物品有体积，求空间为1~m，不带第1~k件的方案数  思路  无法考虑枚举不带某一个物品，对剩下的物品01背包，复杂度直接爆炸 反向思考，可以求解k个物品装满m空间的01背包(每个物品用一次，恰好装满指定体积)，然后再减去必须取某一个物品装满m空间的方案数，就得到去掉某一个物品装满m空间的方案数 设表示去掉某一个物品p背包体积为i的方案数，为体积为i的01背包方案数，那么就是必须选p体积为i的方案数 因此，状态方程可以表示为  代码 #include<bits/stdc++.h> const int N = 2330; using namespace std...

题意  对于一个由0,1构成的矩形，求解其中面积最大的全0子矩形，和全0子正方形  思路  法一：枚举上下左右四个边界，利用二维前缀和，如果前缀和为0就成立  复杂度：   法二：枚举左右边界，对边界内的1按y排序，每两个相邻点+边界构成矩形  复杂度：,(m为1的个数，最多到)   法三：悬线法，将矩形中每个1视为黑点0视为无色点，每个点有一条向上的悬线悬线碰到黑点重新开始计算长度，对于每一条悬线，都有可能成为矩形的上下界   求点(i,j)最长悬线度  求点(i,j)向左最长延伸长度  求点(i,j)向左最长延伸长度  求(i,j)所在的悬线向左最长延伸长度  求(i,j)所在的悬线向左最...

什么是状压  对于题目中一种复杂的状态，如多维，多行，多条路，某种方案，某种集合等压缩成一个整数的过程就是状态压缩 这也可以看作是一个Hash的过程 除去压缩状态的过程，其实它整体和普通的dp差别不大，都是从已知过程推向位置过程 压缩的意义在于把一个一般无法描述的状态，变成一个包含多种信息的状态，而这个状态又可以用二进制数(三进制，四进制也有可能)表示  什么时候考虑状压dp  棋盘格覆盖 类似TSP的路径问题 N比较小(20左右)，且变成N位二进制比较合理

题意  n行m列矩形，用1*2的矩形块填充，有多少种填充方案  思路  依然是棋盘放置一类的问题，考虑一行一行放 对于每一行，上一行竖着放的地方一定放不了，上一行横着放的地方可以竖着放也可以横着放，行内不可能的是把一个横着的拆开，两行间不可能的是，上一行竖着，这一行还放东西 设计状态：横着放记为0，竖着放记为1，竖着放的下一行记为0  这样子新st和旧st做与就可以排除行间冲突 而对于行内，除了上一行是1的位置任意枚举，但是连续的0必须是偶数个，将新st和旧st做或运算，排除原来的1带来的影响，检查剩下的0是不是偶数个连续即可    代码 #include<bits/stdc++.h&g...

#双线dp  双线表示同时有两种状态，且会相互影响  题意  给定M*N的地图，每个点有val，每个点只能走一次 从左上走到右下再走回左上，且向下的过程只能向下向右，向上的过程只能向上向左 走完最多获得的val是多少  思路  思路一：严格按照一圈走无法完成，走下去的过程走过的格子会影响走上去的过程的路径，不妨同时完成，又走上去和走下去完全相同，不妨设两个人同时从起点出发，走到终点，用四维的dp来记录两个人的位置，当两个人重叠的时候就把dp记为无穷小 思路二：可以发现，两个人走的步数是相同的，我们只用记录来表示走了k步，第一个人向下走了i步，第二个人向下走了j步，同样地，当i=j时记为无穷小 ...

题意  n个原子，两个原子i，j碰撞会释放能量，并且j会消失，求n个原子能产生的最大能量  思路  状压dp 每个原子去碰撞的时候，要还剩下哪些原子 也就是每次从还存在的原子中挑出两个原子碰撞，并选择一个消失 最终剩下一个原子结束 状态压缩是你过程，从全满，到只剩一个 特别的，在st=0的时候要人为跳出，否则会re   代码 #include<bits/stdc++.h> // #define int long long using namespace std; int val[15][15]; int dp[1<<13]; /** * dp[i]表示st状态下最大能量...

题意  旅行商问题，在一个若干点的图中，设计一条最短路径，途径所有点 有时最终会要求回到原点  思路  状压dp 访问每一个点的时候需要考虑当前已经访问了哪些点 走到某一个点的最短路径应该是所有(上一步最短路径+上一步所在点到当前点距离)取最小 表示当前状态为st，最后一个点时i的最短路径   代码 #include<bits/stdc++.h> using namespace std; const int N=1020; /** * dp[st][i]表示当前状态为st，最后一个点时i的最短路径 * dp[st][i]=min(dp[st-(1<<(i-1))][j]...

题意  给定N*M的地图，包含山地和平地，山地不能布置炮兵 炮兵会攻击自己上下两格，左右两格的位置，请问在炮兵相互不打架的情况下，地图上最多放置多少炮兵  思路  仍旧按行考虑，预处理行内可行状态 枚举每行可能性，和前两行状态有关，所以是一个三维的dp 表示第i行状态j，i-1行状态为k   代码 #include<bits/stdc++.h> #define endl '\n' using namespace std; /** * dp[i][j][k]表示第i行状态j，i-1行状态为k * dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][p]+nu...

题意  有一个N*N(N<10)的棋盘，其中需要放置K个国王，国王会攻击以他为中心的九宫格范围内的棋子，要是所有国王互不攻击，总共有多少种方案  思路  如果按顺序从上到下，从左到右，每次放置新的国王的时候都需要考虑它左边和上侧的国王，状态过于复杂难以描述 由于N不大可以考虑一行一行放置，这样每一次只需要考虑上一行的状态即可 使用01串描述每一行的状态，提前预处理出来每一行合法的情况，避免动态规划过程中反复枚举 对于不打架这件事  行内：左右不能相邻，如果用a来表示这一行的状态，那就要保证 当前行和上一行：对于上一行的一个棋子，他的正下方，左下，右下不能有棋子，即保证且且   对于动态规...

题意  买彩票，3元一张，中1,2,3,4元的概率相等 买n张，求不亏的概率 输出要求：最简分数，如果概率为0就输出"0/1"，概率为1就输出"1/1"  思路  类似昨天弹球的问题 状态转移可以靠钱勾连 表示买了i张彩票赚j元的可能  最后求一个GCD就行，注意只要买了就会亏，所以概率为1只有可能是一张不买  代码 #include<bits/stdc++.h> using namespace std; long long dp[40][200]; int main(){ int n; cin >> n; dp[1][1]=1; dp[1][2]=1; dp[1][3...

题意  给定n个数，求两个长度为k的不连续区间和最大是多少  思路  选择两个不重叠区间，必然一个在左，一个在右 可以维护一个前缀和，用表示0~i中最大的长度为k的区间的值 然后从后往前遍历，取每一个长为k的区间，为右区间，同时通过在O(1)的时间内获得左区间的最大值，两者相加即可 也可以直接维护一个前缀和一个后缀和，然后维护两个dp，可读性更好一点  代码 #include<bits/stdc++.h> using namespace std; long long dp[302020]; long long a[302020]; int main(){ int T; cin &g...

题意  类似于过河卒  思路  正常实现即可，注意取模  代码 #include<bits/stdc++.h> #define N 3030 #define mod 2333 using namespace std; int a[N][N]; long long dp[N][N]; int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n,m; cin >> n >> m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){...