fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, dp[1005][1005];
  5. string s;
  6. int main() {
  7. 	ios::sync_with_stdio(false); cin.tie(nullptr);
  8. 	cin >> s;
  9. 	n = s.size(); s = " " + s;
  10. 	memset(dp, 0, sizeof(dp));
  11. 	for (int i = 1; i <= n; ++i) dp[i][i] = 1;
  12. 	for (int len = 2; len <= n; ++len) {
  13. 		for (int l = 1; l + len - 1 <= n; ++l) {
  14. 			int r = l + len - 1;
  15. 			dp[l][r] = max(dp[l][r - 1], dp[l + 1][r]);
  16. 			if (s[l] == s[r])
  17. 				dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 2);
  18. 		}
  19. 	}
  20. 	cout << dp[1][n] << '\n';
  21. 	return 0;
  22. }
Success #stdin #stdout 0.01s 7632KB
comments (?)
stdin
copy 
badad
stdout
copy 
3
https://ideone.com/zt1IZy
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!