噫本來今天高高興興
噗
本來今天不想寫博客來著，
哎，看見棟棟大神做題了，
我就跟風過去瞅瞅。。。

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

例如，字符串 character (k=5) 比 pollution (k=4) 更對稱，apple (k=2) 比 pear (k=1) 更對稱。現在給定n個字符串，請將它們按對稱系數排序后從大小輸出 (k相同時按字典序排序)。

輸入描述 Input Description
輸入數據第一行只有一個n，表示有個字符串。

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

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

樣例輸入 Sample Input
5

pineapple

banana

peach

coconut

character

樣例輸出 Sample Output
banana

character

pineapple

coconut

peach

數據范圍及提示 Data Size & Hint
數據范圍：

1<=n<=100

1<=len<=500

1<=k<=len

提示：

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

題意理解沒啥難度
就是求一個字符串的最長回文子序列
注意是子序列不是字串、
字串的話完全可以暴力。
子序列就要用到DP了；；。
噫
DP去死！

。。。。。

對于每個字符串，我們可以將他翻轉；
生成另一個字符串；
之后，只需要求這兩個字符串的最長公共子序列就好了，
用LCS求；

具體做法就是一個二維的DP矩陣
之后枚舉每一個點。

如果對于這個i j 兩字符串相同
f[i][j]=f[i-1][j-1]+1
else
f[i][j]=max(f[i-1][j],f[i][j-1]);

最后得到的f[len][len] 即為答案
注意從1開始枚舉，防止數組越界。

嗯
嗚啦啦啦啦

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<stack> #include<cstdlib> #include<string> #include<bitset> #include<iomanip> #include<deque> #define INF 1000000000 #define fi first #define se second #define N 100005 #define P 1000000007 #define debug(x) cerr<<#x<<"="<<x<<endl #define MP(x,y) make_pair(x,y) using namespace std; int n,m; struct zqm {string s;int k; }q[101]; inline int get_num() { int num = 0; char c; bool flag = false; while ((c = getchar()) == ' ' || c == '\n' || c == '\r'); if (c == '-') flag = true; else num = c - '0'; while (isdigit(c = getchar())) num = num * 10 + c - '0'; return (flag ? -1 : 1) * num; } int js(string s) {int len=s.size(),f[511][511];memset(f,0,sizeof(f));string ss;for(int i=0;i<len;i++){ss[len-i-1]=s[i];}for(int i=1;i<=len;i++){for(int j=1;j<=len;j++){if(s[i-1]==ss[j-1]){f[i][j]=f[i-1][j-1]+1;}else{f[i][j]=max(f[i-1][j],f[i][j-1]);}}}return f[len][len]; } bool cmp(zqm a,zqm b) {if(a.k==b.k){return a.s<b.s;}return a.k>b.k; } int main() {cin>>n;for(int i=1;i<=n;i++){cin>>q[i].s;q[i].k=js(q[i].s);}sort(q+1,q+1+n,cmp);for(int i=1;i<=n;i++){cout<<q[i].s<<endl;} }

。0.0.0

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。