题意 :有排成一行的卡片,每次取一张卡片(不能取开头和结尾的卡片)并获得一个值:该卡片上的数字和它相邻的两张卡片的数字乘积。重复上述操作直到最终只剩下两张卡片,求将得到的所有值加起来最小可以是多少
思路 :考虑用 dp[i][j]
表示从第 i 张卡片到第 j 张卡片中抽卡直到剩余两张能得到的最小值,那么可以枚举区间最后一张抽取的卡牌为 k,状态转移方程得 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j])
,满足 i<j<k
初始化就是区间长度为 1 和 2 的区间无疑都是 0,从区间长度为 3 的计算开始,最终答案就是 dp[1][n]
递推写法
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 #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstdio> #include <cstring> #include <iomanip> #include <string> #include <set> #include <map> #include <vector> #include <queue> #include <stack> #include <sstream> using namespace std ;typedef long long ll;int a[105 ];int dp[105 ][105 ];signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); memset (dp, 0x3f , sizeof dp); int n; cin >> n; for (int i = 1 ; i <= n; ++i) { cin >> a[i]; dp[i][i] = 0 ; dp[i][i+1 ]=0 ; } for (int l = 3 ; l <= n; ++l) { for (int i = 1 ; i + l <= n + 1 ; ++i) { int j = i + l - 1 ; for (int k = i + 1 ; k < j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]); } } cout << dp[1 ][n] << endl ; return 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 37 38 39 40 41 42 #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstdio> #include <cstring> #include <iomanip> #include <string> #include <set> #include <map> #include <vector> #include <queue> #include <stack> #include <sstream> using namespace std ;typedef long long ll;int a[105 ];int dp[105 ][105 ];int func (int l,int r) { if (dp[l][r]!=0x3f3f3f3f )return dp[l][r]; for (int k=l+1 ;k<r;++k) dp[l][r]=min(dp[l][r],func(l,k)+func(k,r)+a[l]*a[k]*a[r]); return dp[l][r]; } signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); memset (dp, 0x3f , sizeof dp); int n; cin >> n; for (int i = 1 ; i <= n; ++i) { cin >> a[i]; dp[i][i] = 0 ; dp[i][i+1 ]=0 ; } cout <<func(1 ,n) << endl ; return 0 ; }
题意 :输入一个字符串,只包括 [ ] ( )
这四种字符,求合法(序列中两种类型的括号都有对应的组合并且不交叉)最长合法括号子序列的长度
1 2 3 4 ((())) ()()() ([][]) ([)]
思路 :考虑用 dp[i][j]
表示以第 i 到第 j 个字符组成的合法子序列的最大长度,那么分为两种转移方式:
第 i 个字符和第 j 个字符对应组合:dp[i][j]=dp[i+1][j-1]+2
否则的话就是分为包含 i 和 j 字符的两部分,枚举分开的位置并加和每个部分取最长:dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])
满足 i<k<j
初始化 dp 数组为 0 为了取最大值同时如果取到未知区间也返还 0,最终答案就是 dp[1][len]
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 #include <cstdio> #include <cstring> #include <iostream> using namespace std ;int dp[105 ][105 ];int main () { char s[105 ]; while (scanf ("%s" , s + 1 ) != EOF) { memset (dp, 0 , sizeof (dp)); int len = strlen (s + 1 ); if (s[1 ] == 'e' ) break ; for (int l = 1 ; l <= len; l++) { for (int i = 1 ; i + l <= len + 1 ; i++) { int j = i + l - 1 ; 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 + 1 ][j]); } } } cout << dp[1 ][len] << endl ; } return 0 ; }
题意 :定义子序列可以是序列中一些不连续的字符组成,请找出给出的序列中最大有多少种回文子序列的组合数量,答案对 1e4+7 取模
思路 :考虑用 dp[i][j]
表示第 i 到 j 字符的回文子序列的组合数量
先不考虑第 i 和 第 j 个字符是否相同,那么 dp[i][j]=(dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]+mod)%mod
,即区间 [i+1,j-1]
的字符和两个新的字符分别组合 多出来的组合数量,中间多算了一次 dp[i+1][j-1]
所以减去一次重叠部分。
再考虑如果第 i 和第 j 个字符相同的话,那么 dp[i][j]
在上述基础上还可以进一步更新 dp[i][j]=(dp[i][j]+dp[i +1][j-1]+1)%mod
,即用区间 [i+1,j-1]
的字符和两个新的字符共同组合 多出来的组合数量
初始化区间长度为 1的序列本身就是回文的所以 dp[i][i]=1
,最终答案就是 dp[1][len]
递推写法
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 #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> using namespace std ;typedef long long ll;const int mod = 1e4 + 7 ;int dp[1005 ][1005 ];signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; for (int _ = 1 ; _ <= t; ++_) { char s[1005 ]; scanf ("%s" , (s + 1 )); cout << "Case " << _ << ": " ; int len = strlen (s + 1 ); memset (dp, 0 , sizeof dp); for (int i = 1 ; i <= len; ++i) dp[i][i] = 1 ; for (int l = 2 ; l <= len; ++l) { for (int i = 1 ; i + l <= len + 1 ; ++i) { int j = i + l - 1 ; dp[i][j] = (dp[i + 1 ][j] + dp[i][j - 1 ] - dp[i + 1 ][j - 1 ] + mod) % mod; if (s[i] == s[j]) dp[i][j] = (dp[i][j] + dp[i + 1 ][j - 1 ] + 1 ) % mod; } } cout << dp[1 ][len] << endl ; } return 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 37 38 39 40 41 42 43 44 45 46 #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> using namespace std ;typedef long long ll;char s[1005 ];int dp[1005 ][1005 ];int len;const int mod = 1e4 + 7 ;int func (int l, int r) { if (dp[l][r] != 0 || l>=r) return dp[l][r]; dp[l][r] = (func(l + 1 , r) + func(l, r - 1 ) - func(l + 1 , r - 1 ) + mod) % mod; if (s[l] == s[r]) dp[l][r] = (dp[l][r] + func(l + 1 , r - 1 ) + 1 ) % mod; return dp[l][r]; } signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; for (int cases = 1 ; cases <= t; ++cases) { cout << "Case " << cases << ": " ; scanf ("%s" , (s + 1 )); len = strlen (s + 1 ); memset (dp, 0 , sizeof dp); for (int i = 1 ; i <= len; ++i) dp[i][i] = 1 ; cout << func(1 , len) << endl ; } return 0 ; }
题意 :存在两个长度相同的字符串 A 和 B,不同的字符代表不同的颜色,每次操作可以将 A 的一段连续的字符用同一个字符代替(即将 A 的一段用一种颜色覆盖),求将 A 涂成 B 至少需要多要操作
思路 : 参考博客
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 #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> using namespace std ;typedef long long ll;int dp[105 ][105 ];int ans[105 ];signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); string a, b; while (cin >> a >> b) { int len = a.length(); for (int i = 0 ; i < len; ++i) dp[i][i] = 1 ; for (int l = 2 ; l <= len; ++l) { for (int i = 0 ; i + l - 1 < len; ++i) { int j = i + l - 1 ; dp[i][j] = dp[i + 1 ][j] + (b[i] != b[j]); for (int k = i; k < j; ++k) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1 ][j] + (b[i] != b[k])); } } } ans[0 ] = (a[0 ] != b[0 ]); for (int i = 1 ; i < len; ++i) { ans[i] = dp[0 ][i]; if (a[i] == b[i]) ans[i] = ans[i - 1 ]; else { for (int j = 0 ; j < i; ++j) ans[i] = min(ans[i], ans[j] + dp[j + 1 ][i]); } } cout << ans[len - 1 ] << endl ; } system("pause" ); return 0 ; }
题意 :有一个队列,其中每个人都有一个愤怒值 D,如果他是第 K 个登场的人那么不开心指数就是 (K-1)*D,现在有一个堆栈可以帮助你更改一段连续的人的出场顺序颠倒。求出借助堆栈操作后整个队列登场后不开心的指数最小是多少
思路 :考虑用 dp[i][j]
表示第 i 到第 j 个人这段区间的相对 i 位置统计的最小不开心指数 ,统计出每个位置的人的愤怒值前缀和,然后枚举第 i 个人出去的位置为 k,那么第 i 个人的不开心值可知 (k-i)*a[i]
,有 k-1 个人是在 k 位置之前出去的,并且有 j-k 个人是在 k 位置之后出去的,他们公有一段不开心值为 (k-i+1)*(sum[j]-sum[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])
初始化合法区间值为最大,不合法区间相当于没人所以为 0,最终答案就是 dp[1][n]
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 #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstdio> #include <cstring> #include <iomanip> #include <string> #include <set> #include <map> #include <vector> #include <queue> #include <stack> #include <sstream> using namespace std ;typedef long long ll;int a[105 ],sum[105 ];int dp[105 ][105 ];signed main () { ios::sync_with_stdio(false ),cin .tie(0 ); int t;cin >>t; for (int cases=1 ;cases<=t;++cases){ int n;cin >>n; for (int i=1 ;i<=n;++i){ for (int j=1 ;j<=n;++j){ if (i<=j)dp[i][j]=0x3f3f3f3f ; else dp[i][j]=0 ; } } for (int i=1 ;i<=n;++i){ cin >>a[i]; sum[i]=sum[i-1 ]+a[i]; } for (int l=1 ;l<=n;++l){ for (int i=1 ;i+l<=n+1 ;++i){ int j=i+l-1 ; 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 #" <<cases<<": " <<dp[1 ][n]<<endl ; } return 0 ; }