有哪些企业有网站有哪些类型,建站之星模块,wordpress仿微信菜单栏,网站背景色区间dp专题
基本思想
区间dp一类的问题往往子问题具有很明显的区间性质,也就是说我们可以通过将子问题定义为整个区间的一个子区间.因为一个大区间可以切分成两段相邻的子区间.从这点出发,我们便可以找到递推关系.
1.纸牌游戏
蜘蛛牌游戏规则是这样的#xff1a;只能将牌拖…区间dp专题
基本思想
区间dp一类的问题往往子问题具有很明显的区间性质,也就是说我们可以通过将子问题定义为整个区间的一个子区间.因为一个大区间可以切分成两段相邻的子区间.从这点出发,我们便可以找到递推关系.
1.纸牌游戏
蜘蛛牌游戏规则是这样的只能将牌拖到比它大一的牌上面AAA最小KKK最大如果拖动的牌上有按顺序排好的牌时那么这些牌也跟着一起移动游戏的目的是将所有的牌按同一花色从小到大排好。为了简单起见我们的游戏只有同一花色的牌但是这样XCX又觉得太简单了于是他把牌数增加到了n(1lt;nlt;100)n(1lt;nlt;100)n(1n100)牌随机的在一行上展开编号从1到nnn把第iii号上的牌移到第j号牌上移动距离为abs(i−j)abs(i-j)abs(i−j)现在你要做的是求出完成游戏的最小移动距离。
题解
采用区间动态规划的方式但是直接进行区间DP是没有任何意义的, 所以实际上我们需要另寻状态的定义方式.
我们需要对数列进行变化一下我们进行dp的区间[a,b][a,b][a,b]定义为高度为aaa到高度为bbb的纸牌叠加到一起所需要的最少距离和。
在一开始我们定义数组arr[x]arr[x]arr[x]中存储的是高度为xxx的纸牌所在的位置。那么状态转移就可以写成dp[a][b]dp[a][j]dp[j1][b]abs(arr[b]−arr[j])dp[a][b] dp[a][j] dp[j1][b] abs(arr[b]-arr[j])dp[a][b]dp[a][j]dp[j1][b]abs(arr[b]−arr[j])
这样的话,问题就迎刃而解了,所以说如何去定义问题是dpdpdp问题的一大难点和关键点.
代码
#includebits/stdc.h
using namespace std;int a[105],n;
int dp[105][105];int main()
{int T;scanf(%d,T);while(T--){scanf(%d,n);for(int i1;in;i){int x;scanf(%d,x);a[x]i;}for(int k2;kn;k){for(int i1;in-k1;i){int li,rik-1;dp[l][r]1e97;for(int jl;jr-1;j)dp[l][r]min(dp[l][r],dp[l][j]dp[j1][r]abs(a[r]-a[j]));}}printf(%d\n,dp[1][n]);}return 0;
}2.Multiplication Puzzle POJ - 1651
在一个序列中拿走一个数字那么得分就是这个数字以及它相邻的两个数字这三个数字的乘积, 求最小得分。
题解
这道题乍一看感觉是区间DP但是需要逆向思考的技巧。
记dp[i][k]dp[i][k]dp[i][k]表示以iii开头的长度kkk的区间。
我们考虑一个区间的时候记录区间的两个端点分别为l,rl,rl,r。
这个区间两侧的端点是不能被拿走的那么我们考虑最后一个被拿走的数字kkk它的得分一定是区间端点的两个数和它的乘积(a[l]∗a[k]∗a[r]a[l]*a[k]*a[r]a[l]∗a[k]∗a[r])。
然后我们考虑区间[l,k][l,k][l,k]之间的情况这个区间被拿的只剩下区间两个端点了所以可以直接用子结构dp[l][k−l1]dp[l][k-l1]dp[l][k−l1]。
同理区间p[k,r]p[k,r]p[k,r]也被拿的只剩下区间的两个端点了直接用子结构dp[k][r−l−k1]dp[k][r-l-k1]dp[k][r−l−k1]
这样的话递推式就非常的清晰了。
dp[i][k]min(dp[i][k],dp[i][j1]dp[ij][k−j]a[i]∗a[ij]∗a[ik−1])dp[i][k] min(dp[i][k],dp[i][j1] dp[ij][k-j] a[i]*a[ij]*a[ik-1])dp[i][k]min(dp[i][k],dp[i][j1]dp[ij][k−j]a[i]∗a[ij]∗a[ik−1])
代码
#include iostream
#include cstdio
#include algorithm
using namespace std;
const int MAX 106;
int dp[MAX][MAX];
int a[MAX];
int n;
int main(){scanf(%d,n);for(int i 0;i n;i){cina[i];}for(int k 3;k n;k){for(int i 0 ;i k n;i){dp[i][k] 1e9;for(int j 1;j k-1;j){dp[i][k] min(dp[i][k],dp[i][j1] dp[ij][k-j] a[i]*a[ij]*a[ik-1]);}}}coutdp[0][n]endl;
}3.括号匹配问题 Brackets POJ - 2955
给定一个括号序列,求最长的合法括号表达式子序列.
题解
再明显不过的区间DP的题目了要求求出给出符号式中最大匹配的括号数。 考虑区间[l,r][l,r][l,r]如果str[l]str[l]str[l]与str[r]str[r]str[r]匹配了那么转移方程为:
dp[l][r]max(dp[l][r],dp[l1][r−1]2)dp[l][r] max(dp[l][r],dp[l1][r-1] 2)dp[l][r]max(dp[l][r],dp[l1][r−1]2)
还有一种情况就是考虑将区间分成2部分
dp[l][r]max(dp[l][r],dp[l][k]dp[k1][r])dp[l][r] max(dp[l][r],dp[l][k]dp[k1][r])dp[l][r]max(dp[l][r],dp[l][k]dp[k1][r])
然后就成了没错就这么简单
代码
#include cstdio
#include cstring
#include algorithm
#include cmath
using namespace std;
const int MAX 105;
char str[MAX];
int dp[MAX][MAX];
int mp[128];
int main(){mp[(] );mp[[] ];while(gets(str)){memset(dp,0,sizeof(dp));if(str[0] e){break;}int n strlen(str);for(int k 2;k n;k){for(int i 0;i k n;i){//左闭右开 for(int j i 1;j i k;j){dp[i][ik] max(dp[i][i k],dp[i][j] dp[j][ik]);if(mp[str[i]] str[ik-1])dp[i][ik] max(dp[i][ik],dp[i1][ik-1]2);}} }printf(%d\n,dp[0][n]);}return 0;
}4.You Are the One HDU - 4283
题目大意就是说给定一个有序序列和一个栈对于队伍前头的一个人有两个操作一个是直接迈向舞台另一个操作就是迈入栈中。在一个时间下迈向舞台的人可以是原始队伍里的人也可以是栈里面的人。举例来说假定队伍此时为 队首4 5队尾栈此时为 栈顶3 2 1 栈底,那么下一个时刻可能是4进入栈中或者4进入舞台或者3从栈中去向舞台。
有nnn个人参加非诚勿扰每个人都有nin_ini的屌丝值如果前面有kkk个人比他早他就会有(k−1)∗(ni)(k−1)*(n_i)(k−1)∗(ni)的不开心值你可以让一些人进入一个小黑屋来改变上场顺序但是小黑屋是类似栈先入后出。求最小不开心值.
题解
我们考虑如下事实
考虑区间[l,r][l,r][l,r]区间长度kr−l1k r-l1kr−l1。
如果区间的第一个元素可能是第111 一直到第 kkk个进入舞台的假设第一个元素是第ppp个进入舞台的1lt;plt;k1lt;plt;k1pk那么我们知道第一个元素一定要先入栈区间[l1,lk−1][l1,lk-1][l1,lk−1]中的元素一定会先第一个元素而进入舞台这样的话就转化到了子结构dp[l1][lk−1]dp[l1][lk-1]dp[l1][lk−1]中去了。
同时[lk,r][lk,r][lk,r]中的元素一定后于第一个元素而进入舞台。他们共同要等待的耗费为p∗sum[lk,r]p*sum[lk,r]p∗sum[lk,r]另外还有一部分耗费为dp[lk][r]dp[lk][r]dp[lk][r]
综上所述得到转移方程
dp[l][r]min(dp[l][r],dp[l1][lk−1](k−1)∗a[lp−1]p∗sum[lk,r]dp[lk][r])dp[l][r] min(dp[l][r],dp[l1][lk-1] (k-1)*a[lp-1] p*sum[lk,r] dp[lk][r])dp[l][r]min(dp[l][r],dp[l1][lk−1](k−1)∗a[lp−1]p∗sum[lk,r]dp[lk][r])
注意代码中用的区间方式为左闭右开。
代码
#include iostream
#include cstring
#include cstdio
#include algorithm
using namespace std;
const int MAX 106;
char strA[MAX];
char strB[MAX];
int dp[MAX][MAX];
int ans[MAX];
int n;
int main(){while(scanf(%s %s,strA,strB) ! EOF){memset(dp,0,sizeof(dp));memset(ans,0,sizeof(ans));n strlen(strA);for(int i 0;i n;i) dp[i][i1] 1;for(int len 2;len n;len){for(int i 0;i len n;i){dp[i][ilen] dp[i1][ilen] (strB[i] strB[ilen-1]?0:1);for(int j i1;j ilen;j){dp[i][ilen] min(dp[i][ilen],dp[i][j]dp[j][ilen]);} }}ans[0] strA[0] strB[0] ? 0:1;for(int i 1;i n;i){ans[i] dp[0][i1];if(strB[i] strA[i])ans[i] min(ans[i],ans[i-1]);for(int j 0;j i;j){ans[i] min(ans[i],ans[j] dp[j1][i1]);}}coutans[n-1]endl;}return 0;
}5.Coloring Brackets CodeForces - 149D
题目大意
给定合法的括号序列让你给括弧上色并且上色时一定要满足3个要求 1每个括号要么被上红色要么被上蓝色要么不上色。 2一对匹配的左右括弧有且只有其中的一个可以被上色。 3相邻的括弧不能被涂上相同的颜色。
题解
首先我们要进行预处理求出每个括号的唯一配对的括号即寻找他们一一对应的关系这个预处理很简单用栈操作一下就可以了 gets(str);stackint stk;int len strlen(str);for(int i 0;i len;i){if(str[i] (){stk.push(i);}else{int p stk.top();stk.pop();mp[p] i;mp[i] p;}}下面我们考虑的区间全部都是配对合法的区间
用一个四维数组dp[l][r][i][j]表示区间[l,r]且l处被涂上i色r处被涂上j色。规定无色为0红色为1蓝色为2
那么我们可以得到下面的状态转移方程
1当区间长度只有2时候两个括弧一定是配对的因为我们考虑的所有区间都是配对合法的区间上色方案是非常好确定的。
dp[l][r][0][1]1;dp[l][r][0][1] 1;dp[l][r][0][1]1; dp[l][r][0][2]1;dp[l][r][0][2] 1;dp[l][r][0][2]1; dp[l][r][1][0]1;dp[l][r][1][0] 1;dp[l][r][1][0]1; dp[l][r][2][0]1;dp[l][r][2][0] 1;dp[l][r][2][0]1;
2当区间的左右括弧是配对的时候判断左右括弧是否匹配用到了预处理得到的结果。则有如下转移方法
if(j ! 1)
dp[l][r][0][1] (dp[l][r][0][1] dp[l1][r-1][i][j])%MOD;
if(j ! 2)
dp[l][r][0][2] (dp[l][r][0][2] dp[l1][r-1][i][j])%MOD;
if(i ! 1)
dp[l][r][1][0] (dp[l][r][1][0] dp[l1][r-1][i][j])%MOD;
if(i ! 2)
dp[l][r][2][0] (dp[l][r][2][0] dp[l1][r-1][i][j])%MOD; 3当区间非左右配对时把区间划分为左右两个各自合法 的区间转移方程是。
dp[l][r][i][j](dp[l][r][i][j]dp[l][k][i][p]∗dp[k1][r][q][j]%MOD)%MOD;dp[l][r][i][j] (dp[l][r][i][j] dp[l][k][i][p] * dp[k1][r][q][j]\%MOD) \% MOD;dp[l][r][i][j](dp[l][r][i][j]dp[l][k][i][p]∗dp[k1][r][q][j]%MOD)%MOD;
这里注意kkk代表的是与l配对的括号那么k1k1k1就是与rrr配对的括号了。这就是预处理的作用
而在动态规划的实现过程中我们发现并非所有的区间都是合法的只有少部分的区间是合法的因此我们用自顶向下的记忆化dp的方法这样可以简化代码的实现。
代码
#include iostream
#include cstdio
#include cstring
#include stack
#include algorithm
#define int long long
using namespace std;
const int MAX 705;
const int MOD 1e9 7;
int used[MAX][MAX];
int mp[MAX];
char str[MAX];
int dp[MAX][MAX][3][3];
void dfs(int l,int r){if(used[l][r]) return ;used[l][r] 1;if(l 1 r){dp[l][r][0][1] 1;dp[l][r][0][2] 1;dp[l][r][1][0] 1;dp[l][r][2][0] 1;return ;}if(mp[l] r){//配对的情况 dfs(l1,r-1);for(int i 0;i 3;i){for(int j 0;j 3;j){if(j ! 1)dp[l][r][0][1] (dp[l][r][0][1] dp[l1][r-1][i][j])%MOD;if(j ! 2)dp[l][r][0][2] (dp[l][r][0][2] dp[l1][r-1][i][j])%MOD;if(i ! 1)dp[l][r][1][0] (dp[l][r][1][0] dp[l1][r-1][i][j])%MOD; if(i ! 2)dp[l][r][2][0] (dp[l][r][2][0] dp[l1][r-1][i][j])%MOD; }}}else{int k mp[l];dfs(l,k);dfs(k1,r);for(int i 0;i 3;i){for(int j 0;j 3;j){for(int p 0;p 3;p){for(int q 0;q 3;q){if(p q 0 || p ! q ){dp[l][r][i][j] (dp[l][r][i][j] dp[l][k][i][p] * dp[k1][r][q][j]%MOD)%MOD;}}} }} }
}
main(){gets(str);stackint stk;int len strlen(str);for(int i 0;i len;i){if(str[i] (){stk.push(i);}else{int p stk.top();stk.pop();mp[p] i;mp[i] p;}}dfs(0,len-1);int ans 0;for(int i 0;i 3;i){for(int j 0;j 3;j){ans (ans dp[0][len-1][i][j])%MOD;}}coutansendl;return 0;
}
