首页 > 代码库 > PAT1040
PAT1040
简单dp,有O(n)做法,这里O(n^2)水过
1 #include <fstream> 2 #include <iostream> 3 #include <vector> 4 #include <string> 5 6 using namespace std; 7 8 #define OJ 9 10 #ifdef OJ11 #define fin cin12 #else13 ifstream fin("in.data");14 #endif15 16 int dp(const string &str){17 int size = str.size();18 vector<vector<bool> > f(size, vector<bool>(size, false));19 20 for (int i = 0; i < size; i++)21 f[i][i] = true;22 23 int res = 1;24 25 for (int len = 2; len <= size; len++){26 for (int s = 0; s <= size - len; s++){27 int e = s + len - 1;28 if (str[s] == str[e] && ((s + 1 > e - 1) || (f[s + 1][e - 1]))){29 f[s][e] = true;30 if (len > res)31 res = len;32 }33 }34 }35 36 return res;37 }38 39 int main(){40 string str;41 getline(cin, str);42 43 cout << dp(str) << endl;44 45 return 0;46 }
PAT1040
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。