Lightoj-1033 Generating Palindromes

L
Problem NameGenerating Palindromes
JudgeLightoj
Problem Linkhttps://lightoj.com/problem/generating-palindromes
Algorithms & DSDynamic Programming , LCS
#include<bits/stdc++.h> using namespace std; typedef long long int ll; #define sf(n) scanf("%lld",&n); #define YES printf("YES\n"); #define NO printf("NO\n"); #define nl printf("\n"); #define PB push_back #define VST(V) sort(V.begin(),V.end()) #define VSTrev(V) sort(V.begin(),V.end(),greater<long long int>()) #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define base1 129 #define base2 137 #define MOD1 1479386893 #define MOD2 1928476349 #define MAX 2000010 ll SET(ll NUM,ll POS) { return NUM | (1<<POS); } bool isOn(ll NUM,ll POS) { return (bool)(NUM & (1<<POS)); } ll mem[110][110]; string s; ll dp(ll left,ll right){ if(left>=right){ return 0; } if(mem[left][right]!=-1){ return mem[left][right]; } ll ans=0; if(s[left]==s[right]){ ans=dp(left+1,right-1); } else{ ans=dp(left+1,right)+1; ans=min(ans,dp(left,right-1)+1); } return mem[left][right]=ans; } int main() { //freopen("1input.txt","r",stdin); fast; ll tcase=1; cin>>tcase; for(ll test=1; test<=tcase; test++) { cin>>s; ll n=s.size(); for(ll i=0;i<=n;i++){ for(ll j=0;j<=n;j++){ mem[i][j]=-1; } } ll ans=dp(0,n-1); cout<<"Case "<<test<<": "<<ans<<"\n"; } return 0; }
Code language: PHP (php)

About the author

Sheikh Arman Hossain
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!