題目描述?Description

? ? ? 小A想買一頂新帽子，商店里有n個帽子 (1<=n<=100)，每頂帽子上有一個字符串，字符串的長度為len (1<=len<=500)。她認為每頂帽子上的字符串看起來越對稱則代表這頂帽子更漂亮。根據(jù)每個字符串，我們可以算出其對稱系數(shù)k (即最長對稱子序列的長度) 來比較各頂帽子在小A心中的漂亮程度。

? ? ? 例如，字符串 character (k=5) 比 pollution (k=4) 更對稱，apple (k=2) 比 pear (k=1) 更對稱。

? ? ? 現(xiàn)在給定n個字符串，請將它們按對稱系數(shù)排序后從大小輸出 (k相同時按字典序排序)。

輸入描述?Input Description

輸入數(shù)據(jù)第一行只有一個n，表示有個字符串。

接下來有n行，每行一個字符串。

輸出描述?Output Description

輸出有n行，每行一個字符串，表示按對稱系數(shù)從大到小排序后的字符串，對稱系數(shù)相同時按字典序排序。

樣例輸入?Sample Input

5

pineapple

banana

peach

coconut

character

樣例輸出?Sample Output

banana

character

pineapple

coconut

peach

數(shù)據(jù)范圍及提示?Data Size & Hint

數(shù)據(jù)范圍：

1<=n<=100

1<=len<=500

1<=k<=len

提示：

對稱系數(shù)k是指最長對稱子序列的長度，非最長對稱子串的長度。

分析：

求最長對稱子串，即一個子串倒著讀和原來的子串結果一樣。那么原子串屬于 輸入字符串正序，那么尋找對稱的串，從逆序中尋找即可。所以

k值為求一個字符串，和你逆序的最長公共子串的長度即可。 然后按要求排序輸出。

代碼：

#include <iostream> #include<string> #include<algorithm> #include<cstring> #include<string> #include<queue> using namespace std;struct SYSMMETRY{string str;int coeffi; };struct cmpSysmtry{bool operator()(SYSMMETRY o1,SYSMMETRY o2){if(o1.coeffi != o2.coeffi)return o1.coeffi < o2.coeffi;return o1.str > o2.str;} };priority_queue<SYSMMETRY, vector<SYSMMETRY>, cmpSysmtry> pq;int f[501][501];int lcs2(string &s1,string &s2) {memset(f,0,sizeof(f));for(int i = 0; i < s1.size(); i++){for(int j = 0; j < s2.size(); j++){if(s1.at(i) == s2.at(j)){if(i-1 >= 0 && j-1 >= 0)f[i][j] = f[i-1][j-1] + 1;elsef[i][j] = 1;} else{int a = 0, b = 0;if(i-1 >= 0) a = f[i-1][j];if(j-1 >= 0) b = f[i][j-1];f[i][j] = max(a,b);}} }return f[s1.size()-1][s2.size()-1]; }void print(){while(!pq.empty()){cout<<pq.top().str<<endl;pq.pop();} }int main() {SYSMMETRY input;string s1;int n = 0;cin >> n;for(int i = 1 ; i <= n; i++){cin >> input.str;s1 = input.str;reverse(s1.begin(),s1.end());memset(f,-1,sizeof(f));input.coeffi = lcs2(input.str,s1);pq.push(input);}print();return 0; }

總結

以上是生活随笔為你收集整理的2980 买帽子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。