PAT 1040 最长回文串

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

上一篇:PAT (Advanced Level) Practice 1040 Longest Symmetric String (25 分) 凌宸1642


下一篇:openstack中数据库连接数太多--pymysql.err.OperationalError,1040, u'Too many connections'