PAT 1040 最长回文串
dp,练手
代码:
#include <bits/stdc++.h>
using namespace std;
string s;
const int maxn = 1005;
int dp[maxn][maxn];
int dpf(){
int max = 1;
for(int r = 2;r <= s.size();r++){
for(int i = 0;i <= s.size()-r;i++){
dp[i][i+r] = dp[i+1][i+r-1] * (s[i]==s[i+r-1]);
if(dp[i][i+r]) max = r;
}
}
return max;
}
int main(){
char c;
while(true){
if((c = getchar()) =='\n') break;
s += string(1,c);
}
fill(dp[0], dp[0]+maxn*maxn, 1);
if(s==""){
cout<<0<<endl;
return 0;
}
cout<<dpf()<<endl;
}
12ms