「kuangbin带你飞」专题二十二 区间DP
layout: post 传送门 B.LightOJ - 1422 Halloween Costumes题意按顺序参加舞会,参加一个舞会要穿一种衣服,可以在参加完一个舞会后套上另一个衣服再去参加舞会,也可以在参加一个舞会的时候把外面的衣服脱了,脱到合适的衣服,但是脱掉的衣服不能再穿,参加完全部舞会最少穿多少次衣服 题解区间dp,dp【i】【j】表示区间i->j之间的衣服数 起始情况i->i要穿一件衣服 可以从后往前推 如果K的衣服和I的衣服一样代表 到K的时候可以把衣服脱到剩I的时候 这样就是K前面的衣服加上K->J的衣服 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=998244353; const int maxn=1e6+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;} int lcm(int a,int b){return a*b/gcd(a,b);} int dp[110][110]; int a[110]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int t; cin>>t; int cnt=1; while(t--){ int n; cin>>n; memset(dp,sizeof(dp)); for(int i=1;i<=n;i++)cin>>a[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; if(a[i]==a[j])dp[i][j]=dp[i][j-1]; for(int k=i+1;k<j;k++){ if(a[i]==a[k]){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); // cout<<"i=="<<i<<" j=="<<" dp[i][j]="<<dp[i][j]<<endl; } } } } cout<<"Case "<<cnt++<<": "; cout<<dp[1][n]<<endl; } return 0; } C.POJ - 2955 Brackets题意给出一个的只有‘(‘,‘)‘,‘[‘,‘]‘四种括号组成的字符串,求最多有多少个括号满足题目里所描述的完全匹配。 题解用dp[i][j]表示区间[i,j]里最大完全匹配数。 #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=998244353; const int maxn=1e3+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; int gcd(int a,b);} char s[maxn]; int dp[maxn][maxn]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); while(cin>>s+1){ if(s[1]=='e')break; memset(dp,sizeof(dp)); int n=strlen(s+1); for(int len=2;len<=n;len++) for(int i=1;i<=n;i++){ int j=i+len-1; if(j>n)break; if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']'){ dp[i][j]=dp[i+1][j-1]+2; } for(int k=i;k<j;k++){ dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]); } } cout<<dp[1][n]<<endl; } return 0; } D.CodeForces - 149D Coloring Brackets题意给你一个只有括号的字符串, 1,每个括号只有三种选择:涂红色,涂蓝色,不涂色。 2,每对括号有且仅有其中一个被涂色。 3,相邻的括号不能涂相同的颜色,但是相邻的括号可以同时不涂色。 题解因为是一个合法的括号序列。 所以每个括号与之匹配的位置是一定的。 那么就可以将这个序列分成两个区间。 (L - match[L] ) (match[L]+1,R) 用递归先处理小区间,再转移大区间。 因为条件的限制,所以记录区间的同时,还要记录区间端点的颜色。 然后就是一个递归的过程。 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=1e9+7; const int maxn=1e6+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; int gcd(int a,b);} ll dp[800][800][3][3]; int a[110]; ll ans; char s[800]; int match[800]; int stk[800]; void dfs(int l,int r){ if(l+1==r){ dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1; return; } if(match[l]==r){ dfs(l+1,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[l+1][r-1][i][j])%mod; if(j!=2)dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])%mod; if(i!=1)dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])%mod; if(i!=2)dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])%mod; } } } else{ dfs(l,match[l]); dfs(match[l]+1,r); for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ for(int k=0;k<3;k++){ for(int p=0;p<3;p++){ if(j&&j==k)continue; dp[l][r][i][p]=(dp[l][r][i][p]+(dp[l][match[l]][i][j]*dp[match[l]+1][r][k][p]%mod)%mod)%mod; } } } } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int t; int cnt=1; cin>>s+1; int n=strlen(s+1); memset(match,sizeof(match)); int top=-1; for(int i=1;i<=n;i++){ if(s[i]=='(')stk[++top]=i; else match[stk[top--]]=i; } memset(dp,sizeof(dp)); dfs(1,n); ans=0; for(int i=0;i<3;i++) for(int j=0;j<3;j++){ ans=(ans+dp[1][n][i][j])%mod; } cout<<ans<<endl; return 0; } E.POJ - 1651 Multiplication Puzzle题意给出N个数,每次从中抽出一个数(第一和最后一个不能抽),每次的得分为抽出的数与相邻两个数的乘积,直到只剩下首尾两个数为止,问最小得分是多少 题解1枚举起点和终点,但是这次长度要从3开始了因为中间必要取一个 #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=998244353; const int maxn=1e2+50; const int inf=0x3f3f3f3f; int gcd(int a,b);} int a[maxn]; int dp[maxn][maxn]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n; while(cin>>n){ for(int i=1;i<=n;i++)cin>>a[i]; memset(dp,sizeof(dp)); for(int len=3;len<=n;len++){ for(int i=1;i<=n;i++){ int j=i+len-1; if(j>n)continue; dp[i][j]=inf; for(int k=i+1;k<j;k++){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]); //cout<<"i=="<<i<<" j="<<j<<" k=="<<k<<" dp[i][j]="<<dp[i][j]<<endl; } } } cout<<dp[1][n]<<endl; } return 0; } 题解2记忆化搜索 #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; #define pp pair<int,b);} int a[maxn]; int dp[maxn][maxn]; int dfs(int s,int t){ if(dp[s][t]!=-1)return dp[s][t]; if(t-s<=1)return 0; int ans=inf; for(int i=s+1;i<t;i++) ans=min(ans,dfs(s,i)+dfs(i,t)+a[s]*a[t]*a[i]); dp[s][t]=ans; return ans; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n; while(cin>>n){ for(int i=1;i<=n;i++)cin>>a[i]; memset(dp,-1,sizeof(dp)); cout<<dfs(1,n)<<endl; } return 0; } G.HDU - 4283 You Are the One题意有一个队列,每个人有一个愤怒值D,如果他是第K个上场,不开心指数就为(K-1)*D。但是边上有一个小黑屋(其实就是个堆栈),可以一定程度上调整上场程序 题意对于区间 [x,y] 中的数字 a[x],有可能第1个出栈,也有可能最后一个出栈,如果第k个出栈的话前i+1->k个数字要按照顺序出栈,然后a[x]出栈,[k+1,y]出栈。对于a[x]要加上a[x]×(k-i)的花费,对于[x+1,y]要加上sum(x+1,y) * (i-x+1)的额外花费。 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,b);} int dp[110][110]; int a[110]; int ans[110]; int sum[110]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int t; int cnt=1; cin>>t; while(t--){ int n; cin>>n; memset(dp,sizeof(dp)); memset(sum,sizeof(sum)); for(int i=1;i<=n;i++)cin>>a[i],dp[i][i]=0,sum[i]=sum[i-1]+a[i]; for(int len=2;len<=n;len++) for(int i=1;i<=n;i++){ int j=i+len-1; if(j>n)break; dp[i][j]=inf; for(int k=i;k<=j;k++){ dp[i][j]=min(dp[i][j],a[i]*(k-i)+(k-i+1)*(sum[j]-sum[k])+dp[i+1][k]+dp[k+1][j]); } } cout<<"Case #"<<cnt++<<": "; cout<<dp[1][n]<<endl; } return 0; } H.HDU - 2476 String painter题意给出两个长度相同的字符串a,b.对a可以进行区间更新(选择一个区间,把这个区间全部更新成相同的字符),问要最少操作a多少次,a才能等于b? 题解先处理一下b串 用DP存b串i到j的改变次数 然后再对a串进行状态转移。对于串b,最要是看两个相同字符之间的区间了。我们可以预处理出来改变区间[x,y]里面的字符,操作的最小次数用dp[x,y]来存储。 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,b);} int dp[110][110]; char a[110],b[110]; int ans[110]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); while(cin>>a>>b){ memset(dp,sizeof(dp)); int n=strlen(b); for(int i=0;i<n;i++)dp[i][i]=1; for(int len=2;len<=n;len++) for(int i=0;i<n;i++){ int j=i+len-1; if(j>=n)break; if(b[i]==b[j])dp[i][j]=dp[i+1][j]; else dp[i][j]=dp[i+1][j]+1; for(int k=i+1;k<j;k++){ if(b[k]==b[i]) dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]); } } ans[0]=a[0]==b[0]?0:1; for(int i=1;i<n;i++){ ans[i]=dp[0][i]; if(a[i]==b[i])ans[i]=min(ans[i],ans[i-1]); for(int j=0;j<i;j++) ans[i]=min(ans[i],ans[j]+dp[j+1][i]); } cout<<ans[n-1]<<endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |