Editorial for Đếm số Palindrome
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
uses math; var s:string; i,j,n:longint; f:array[0..255] of longint; d:array[0..255,0..255] of boolean; begin readln(s); n:=length(s); for i:=1 to n do d[i,i]:=true; for i:=1 to n-1 do if s[i]=s[i+1] then d[i,i+1]:=true; for j:=3 to n do for i:=1 to n-j+1 do d[i,i+j-1]:=d[i+1,i+j-2] and (s[i]=s[i+j-1]); for i:=1 to n do f[i]:=300; for i:=1 to n do for j:=0 to i-1 do if d[j+1,i] then f[i]:=min(f[i],f[j]+1); writeln(f[n]); end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N 260 char s[N]; int f[N][N]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif scanf("%s",s); int n = strlen(s); fo(len,1,n) rep(i,n+1-len) { int j = i+len-1; if(len == 1) f[i][j] = 1; else if(len == 2) f[i][j] = s[i] == s[j] ? 1 : 2; else if( s[i] == s[j] && f[i+1][j-1] == 1 ) f[i][j] = 1; else { f[i][j] = len; fo(k,i,j-1) f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]); } } printf("%d\n", f[0][n-1]); return 0; }
Code mẫu của ladpro98
#include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <cstring> #define REP(i, a, b) for(int i = (a); i <= (b); ++i) #define REPD(i, a, b) for(int i = (a); i >= (b); --i) #define endl '\n' const int N = 500; using namespace std; bool isPalin[N][N]; int f[N], trace[N]; char s[N]; int main() { scanf("%s", s + 1); int n = strlen(s + 1); REP(i, 1, n) isPalin[i][i] = isPalin[i + 1][i] = 1; REPD(i, n, 1) REP(j, i + 1, n) isPalin[i][j] = s[i] == s[j] && isPalin[i + 1][j - 1]; REP(i, 1, n) { f[i] = n; REPD(j, i, 1) if (isPalin[j][i] && f[i] > f[j - 1]) { f[i] = f[j - 1] + 1; trace[i] = j; } } cout << f[n] << endl; /* vector<string> ans; for (int i = n; i; i = trace[i] - 1) { string palin = ""; REP(j, trace[i], i) palin += s[j]; ans.push_back(palin); } reverse(ans.begin(), ans.end()); for(vector<string>::iterator it = ans.begin(); it != ans.end(); ++it) cout << *it << endl; */ return 0; }
Code mẫu của RR
#include <iostream> #include <algorithm> #define FOR(i,a,b) for(int i=a; i<=b; i++) using namespace std; int main() { char s[300]; gets(s); int n = strlen(s)-1; int f[300]; bool dx[300][300]; FOR(i,0,n) { dx[i][i] = true; if (i) dx[i][i-1] = true; } FOR(l,1,n) FOR(i,0,n-l) { int j = i + l; dx[i][j] = dx[i+1][j-1] & (s[i] == s[j]); } FOR(i,0,n) { if (dx[0][i]) f[i] = 1; else f[i] = n+10; FOR(j,0,i-1) if (dx[j+1][i]) f[i] = min(f[i], f[j]+1); } printf("%d",f[n]); return 0; }
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> #include <string.h> int main() { // freopen("COUNTPL.in","r",stdin); int f[256]; bool a[256][256]; char s[256]; scanf("%s",s); int n = strlen(s); for(int i = 0;i<n;i++) { for(int j = 0;j<=n-1-i;j++) { if(i==0) a[j][j]= true; else if(i==1) { if(s[j]==s[j+1]) a[j][j+1]=true; else a[j][j+1]= false; } else { if(s[j]!=s[j+i]) a[j][j+i]=false; else a[j][j+i]=a[j+1][j+i-1]; } } } f[0]=1; for(int i = 1;i<=n-1;i++) { if(a[0][i]) f[i]=1; else { int min = 1000; for(int j = 1;j<=i;j++) if(a[j][i] && f[j-1]+1<min) min = f[j-1]+1; f[i]=min; } } printf("%d",f[n-1]); //getch(); }
Code mẫu của ll931110
#include <cmath> #include <cstring> #include <iostream> #include <string> using namespace std; int F[260]; string S; bool pal[260][260]; int rec(int x) { if (x < 0) return 0; if (F[x] > -1) return F[x]; int best = x; for (int i = x; i >= 0; i--) if (pal[i][x]) best = min(best,rec(i - 1)); return F[x] = 1 + best; } int main() { // freopen("pl.in","r",stdin); // freopen("pl.ou","w",stdout); cin >> S; int n = S.size(); for (int i = 0; i < n; i++) pal[i][i] = true; for (int i = 0; i < n - 1; i++) pal[i][i + 1] = (S[i] == S[i + 1]); for (int len = 3; len <= n; len++) for (int i = 0; i <= n - len; i++) { int j = i + len - 1; pal[i][j] = ((S[i] == S[j]) && pal[i + 1][j - 1]); } memset(F,-1,sizeof(F)); printf("%d\n", rec(n - 1)); }
Comments