首页 > 代码库 > 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