POJ 2955 Brackets：最简单的区间DP，括号序列
LA4394 String Painter：两层区间DP，难度较大
POJ 3744 Scout YYF I：概率型递推配合矩阵快速幂加速
POJ 2096 Collecting Bugs：优惠券问题的二维情形
UVA 10911 Forming Quiz Teams：最优配对问题
LA3725 Hie with the Pie：TSP问题
POJ 1655 Balancing Act：求树的重心
Codeforces 461B Appleman and Tree：最大独立集问题的变种
给定两个长度相等，只有小写字母构成的字符串s和t，每步可以把s的一个连续子串“刷”成同一个字母，问至少多少步才能把s变成t。
两层区间DP。
首先忽略原始串s，只去看目标串t，设dp1[i][j]表示从什么都没有的情况下利用刷子规则构造出目标串t的i到j这一段所需要的最小操作次数。这里着眼于“最后一次操作”进行阶段的划分。
dp1的状态转移：
接下来引入原始串s，令dp2[i]表示把原始串1到i构造成目标串1到i的部分所需要的最小的操作次数。这里有状态转移：
这里的意思是如果在第i位两个串对应字符相等，可以选择无需对这一位进行操作
这里的意思是假设最后k位使用不考虑原始状态的构造方法，前面继承最优解。为什么要这样做？考虑fabcf这样的区间，一种较好的策略是先都刷成f，然后分别刷好abc，如果你选择这么做了，相当于已经无视了原来串的样子，因为第一步已经将全部中间字符都刷成f了。
|
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 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int dp[105][105]; int res[105]; int main(){ string a,b; while(cin >> a >> b){ memset(dp,0,sizeof(dp)); memset(res,0,sizeof(res)); int n = (int)a.size(); for(int i = 1;i <= n;i++){ dp[i][i] = 1; } for(int i = n-1;i >= 1;i--){ for(int j = i+1;j <= n;j++){ dp[i][j] = dp[i+1][j] + 1; for(int k = i+1;k <= j;k++){ if(b[i-1] == b[k-1]){ dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]); } } } } for(int i = 1;i <= n ;i++){ res[i] = min(dp[1][i],res[i-1]+(a[i-1] != b[i-1])); for(int j = 1;j <= i;j++){ res[i] = min(res[i],res[j]+dp[j+1][i]); } } cout << res[n] << endl; } return 0; } |
经典问题：TSP。
给出了n个城市，求一条最短的路径，使得经过每个城市一次且仅一次，最后回到起点。
状态压缩DP。分析问题可知道是一个多阶段决策过程，每个阶段“状态”包括了可以用已经走了哪些点，和当前站在哪个点，决策就是接下来走哪个点。
状态表示：dp[二进制位，表示目前已经走过那些点][最后走的点的序号] = 从起点出发走过的最短路程
答案：min{dp[走过全部点的状态][枚举各个可能的最后走的点i] + dis(i,起点)}
边界：dp[0][起点] = 0,其它都是INF
状态转移：用dp[S][i] + dis(i,j) 去尝试更新dp[S|j][j]
|
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; int n; long long dis[12][12]; long long dp[12][4096]; void floyd_warshall(){ for (int k = 0; k <=n;k++) { for(int i = 0; i<= n; i++){ for(int j = 0; j<=n ;j++){ if(dis[i][k] + dis[k][j] < dis[i][j]){ dis[i][j] = dis[i][k] + dis[k][j]; } } } } } long long solve(){ memset(dp, 0x3f, sizeof(dp)); for(int i = 0; i < (1 << n) ;i++){ int cnt = 0,lst = 0; for(int j = 1; j <= n; j++){ if(i & (1 << (j-1))){ cnt++; lst = j; } } if(cnt <= 1){ dp[lst][i] = dis[0][lst]; }else{ for(int j = 1; j <= n; j++){ if(i & (1 << (j-1))){ for(int k = 1; k <= n; k++){ if(j != k && i & (1 << (k-1))){ dp[j][i] = min(dp[j][i],dp[k][i^(1 << (j-1))] + dis[k][j]); } } } } } } long long ret = 0x3f3f3f3f3f3f3f3f; for(int i = 1; i<=n;i++){ ret = min(ret,dp[i][(1 << n)-1] + dis[i][0]); } return ret; } int main(){ //freopen("testdata.in", "r", stdin); while(scanf(" %d",&n) != EOF && n){ for(int i = 0; i <= n ;i++){ for(int j =0;j <= n; j++){ scanf(" %lld",&dis[i][j]); } } floyd_warshall(); printf("%lld\n",solve()); } return 0; } |
经典模型“最优配对问题”，给出了平面上若干个点，你要把牠们两两配对，使得每一对中两点距离之和最小。
分析问题：我们发现，本问题可以着眼于“最后一次配对”，是一个多阶段决策。不妨考虑当最后一次选择拿i号点去和j号点去配对,得到了某种状态时可以得到的最优解。
状态表示：dp[当前状态下各个点是否已经配对][最后一次配对的点i][最后一次配对的点j]
我们发现这个状态设的太繁了，假如我们要配对a和b这两个点，那么在所有的配对状态里面都要算入a和b的距离，在所有没配对状态里都不可以算入a和b的距离，后两个维度强行决定了一组点的配对情况，然而并没有什么意义，因为后两个维度的信息已经包括进了第一个维度里，我们只要想办法让第一个维度可以表达出决策的“分阶段”特性，能够识别出最后一步是什么就可以。
于是我们重设状态：dp[当前状态下各个点是否已经配对]并且规定在每个状态中，最低位为1对应的那个点是我们最后一次操作的点。
这样有状态转移：dp[S] = min{dis(i,j) + dp[S^i^j]} 在这里S是二进制表示的状态，i,j是假定的最后一次配对的点对，其中规定i一定是S中最低位的那个点，dis表示求距离，S^i^j表示将二进制表示的状态中i,j对应的位设成零之后得到的二进制状态
|
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 <iostream> #include <cstdio> using namespace std; int n; struct Student{ double x; double y; string name; } stu[17]; double dis(Student &a,Student &b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double dp[17][100000]; double solve(){ memset(dp, 0x77, sizeof(dp)); dp[0][0] = 0; dp[1][0] = 0; dp[1][1] = 0; for(int i = 2;i <= n; i++){ for(int j = 0; j < (1 << i) ;j++){ if(j&(1 << (i-1))){ for(int k = 1; k < i; k++){ if(j & (1 << (k-1))){ dp[i][j] = min(dp[i][j],dp[i-1][j^(1 << (i-1))^(1 << (k-1))] + dis(stu[i], stu[k])); } } }else{ dp[i][j] = dp[i-1][j]; } } } return dp[n][(1 << n)-1]; } int main(){ int caseCnt = 0; while(cin >> n){ if(!n){ break; } n *= 2; caseCnt++; for(int i = 1; i <= n; i++){ cin >> stu[i].name >> stu[i].x >> stu[i].y; } cout << "Case " << caseCnt << ": " << fixed << setprecision(2) << solve() << endl; } return 0; } |
给出一个由小括号喝中括号组成的括号序列，定义正规括号序列为(),[],(s),[s],其中s也是正规括号序列。求最长正规括号序列的长度。
考虑区间DP，设计状态时着眼于“最后一次加括号”。
状态表示：dp[i][j] = 从 i 到 j 的（包含i,j）最长的括号序列长度。
状态转移：
答案：dp[1][len]
初始化：直接令整个dp数组都为0，既可以完成初始化，也可以无效化所有无效状态。
|
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 |
#include <stdio.h> #include <iostream> using namespace std; const int MAXN = 105; char str[MAXN]; int len; int dp[MAXN][MAXN];//dp[from][to] = maximum rectified seq len btw from and to void solve(){ memset(dp, 0, sizeof(dp)); for(int i = len; i >= 1; i--){ dp[i][i] = 0; for(int j = i+1; j <= len; j++){ dp[i][j] = dp[i][j-1]; for(int k = i; k <= j; k++){ if ((str[k-1] == '(' && str[j-1] == ')') || (str[k-1] == '[' && str[j-1] == ']')) { dp[i][j] = max(dp[i][j],dp[i][k-1] + 2 + dp[k+1][j-1]); } } } } printf("%d\n",dp[1][len]); } int main(){ while(scanf(" %s",str) != EOF){ if(str[0] == 'e'){ break; } len = (int)strlen(str); solve(); } return 0; } |
以下a指一个二进制位。
NOT
如果智商正常应该不会不能理解取反运算吧
AND
由此可见善加利用AND运算，可以保证某个二进制数的特定位为0，其余的位保持原样。
OR
由此可见善加利用OR运算，可以保证某个二进制数特定位为1，其余位维持原样。
XOR
XOR/异或运算具有重要性质:
SHL/SHR
左移运算相当于除以2，右移运算相当于乘2.
while(~scanf(” %d”,&n)){}
while(scanf(” %d”,&n) != EOF){}
两种形式等价
if a&1 == 1 then a is odd
if a&1 == 0 then a is even
lowbit(x) = x&(-x)
mask = (1 << n) – 1
INTMAX = ~(1 << 31)
LLMAX = ~(1ll << 63)
INTMIN = 1 << 31
LLMIN = 1ll << 63
memset(dp,0x3f,sizeof(dp))
a＝ a ^ b
b = a ^ b
a = a ^ b
abs(n) = (n ^ (n >> 31)) – (n >> 31)
max(a,b) = b & ((a-b) >> 31) | a & (~(a-b) >> 31)
min(a,b) = a & ((a-b) >> 31) | b & (~(a-b) >> 31)
用二进制位表示集合是很简单也是很直观的，直接举个例子：假设全集是{a,b,c,d,e,f,g,h}，这样我们一共有8种不同的元素，怎么表示{a,c,e}这个集合呢，很简单，我们拿出8个二进制位，从左到右分别表示“a,b,c,d,e,f,g,h”，那么{a,c,e}就可以用二进制”10101000″ 表示。
加入元素：使用“或等”运算
删除元素：使用“和等”运算
确认元素是否在内：使用“和”运算
并集：使用“或”运算
交集：使用“和”运算
补集：先使用“取反”运算，再使用“和”运算
开关：使用“异或”运算
枚举全部的集合形态：从0枚举至11111111…
枚举某个集合的自己：-1，然后和求子集的集合做“和等”
i i^1互为反向边，要求插边时必须同时插入正边和反边，边数组编号从2的倍数或0开始。
令根节点为1
编号x的节点的左儿子编号: (x << 1)
编号x的节点的右儿子编号: (x << 1) + 1
编号x的节点的父亲编号: (x >> 1)
编号x的节点的兄弟编号: (x ^ 1)
使用堆存储，根节点编号为1，如果a^b=1，则两个点必定同属一个父亲
先坑着，看需求
模运算很慢，所以我们用XOR代替mod2。
int tick = 0;
for(){
dp[tick^1] = dp[tick];
tick ^= 1;
}
这里暂时不详细提供代码了。