南宁网站关键词推广,微商城网站建设平台合同范本,新开传奇网站合击,设计师入门必学软件个人心得#xff1a;今天就做了这些区间DP#xff0c;这一题开始想用最长子序列那些套路的#xff0c;后面发现不满足无后效性的问题#xff0c;即#xff08;#xff0c;#xff09;的配对 对结果有一定的影响#xff0c;后面想着就用上一题的思想就慢慢的从小一步一步…个人心得今天就做了这些区间DP这一题开始想用最长子序列那些套路的后面发现不满足无后效性的问题即的配对 对结果有一定的影响后面想着就用上一题的思想就慢慢的从小一步一步递增后面想着越来越大时很多重复应该要进行分割 后面想想又不对就去看题解了没想到就是分割还是动手能力太差还有思维不够。 1 for(int j0;jich.size();j)
2 {
3 if(check(j,ji))
4 dp[j][ji]dp[j1][ji-1]2;
5 for(int mj;mji;m)
6 dp[j][ji]max(dp[j][ji],dp[j][m]dp[m1][ji]);
7 } 分割并一次求最大值。动态规划真的是一脸懵逼样多思考多瞎想吧呼~ We give the following inductive definition of a “regular brackets” sequence: the empty sequence is a regular brackets sequence,if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, andif a and b are regular brackets sequences, then ab is a regular brackets sequence.no other sequence is a regular brackets sequenceFor instance, all of the following character sequences are regular brackets sequences: (), [], (()), ()[], ()[()] while the following character sequences are not: (, ], )(, ([)], ([(] Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 i2 … im ≤ n, ai1ai2 … aim is a regular brackets sequence. Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])]. Input The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed. Output For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line. Sample Input ((()))
()()()
([]])
)[)(
([][][)
end Sample Output 6
6
4
0
6 1 #includeiostream2 #includecstdio3 #includecmath4 #includecstring5 #includeiomanip6 #includestring7 #includealgorithm8 using namespace std;9 int money[205];
10 int dp[205][205];
11 string ch;
12 const int inf999999;
13 int check(int i,int j){
14 if((ch[i](ch[j]))||(ch[i][ch[j]]))
15 return 1;
16 return 0;
17 }
18 void init(){
19 for(int i0;ich.size();i)
20 for(int j0;jch.size();j)
21 dp[i][j]0;
22 }
23 int main(){
24 int n,m;
25 while(getline(cin,ch,\n)){
26 if(chend) break;
27 init();
28 for(int k0;kch.size()-1;k)
29 if(check(k,k1))
30 dp[k][k1]2;
31 else
32 dp[k][k1]0;
33 for(int i2;ich.size();i)
34 {
35 for(int j0;jich.size();j)
36 {
37 if(check(j,ji))
38 dp[j][ji]dp[j1][ji-1]2;
39 for(int mj;mji;m)
40 dp[j][ji]max(dp[j][ji],dp[j][m]dp[m1][ji]);
41 }
42
43 }
44 coutdp[0][ch.size()-1]endl;
45 }
46 return 0;
47 } 转载于:https://www.cnblogs.com/blvt/p/7371994.html
