Advertisement
Guest User

Untitled

a guest
Jun 27th, 2017
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.74 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define LL long long
  4.  
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9. string s;
  10. cin >> s;
  11. int l = s.length();
  12. int dp[l+1][l+1];
  13. memset(dp,0,sizeof(dp));
  14. for(int i = 0; i < l; i++)
  15. dp[i][i] = 1;
  16. for(int i = 2; i <= l; i++)
  17. {
  18. for(int j = 0; j < l-i+1; j++)
  19. {
  20. int k = i+j-1;
  21. if(s[j] == s[k])
  22. {
  23. dp[j][k] = 2+dp[j+1][k-1];
  24. }
  25. else
  26. {
  27. dp[j][k] = max(dp[j+1][k],dp[j][k-1]);
  28. }
  29. }
  30. }
  31. int ans = abs(l-dp[0][l-1]);
  32. if(ans&1)
  33. {
  34. cout << "Second\n";
  35. }
  36. else
  37. {
  38. cout << "First\n";
  39. }
  40. return 0;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement