1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define mz(array) memset(array, 0, sizeof(array))14 #define mf1(array) memset(array, -1, sizeof(array))15 #define minf(array) memset(array, 0x3f, sizeof(array))16 #define REP(i,n) for(i=0;i<(n);i++)17 #define FOR(i,x,n) for(i=(x);i<=(n);i++)18 #define RD(x) scanf("%d",&x)19 #define RD2(x,y) scanf("%d%d",&x,&y)20 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)21 #define WN(x) printf("%d\n",x);22 #define RE  freopen("brackets.in","r",stdin)23 #define WE  freopen("brackets.out","w",stdout)24 #define mp make_pair25 #define pb push_back26 #define pf push_front27 #define ppf pop_front28 #define ppb pop_back29 typedef long long ll;30 typedef unsigned long long ull;31 32 const double pi=acos(-1.0);33 const double eps=1e-10;34 35 const ll MOD=1e9+7;36 ll MMOD = MOD*1000000;37 const int maxn=1111111;38 39 int a[maxn];40 int n;41 42 ll f[maxn];43 int d[maxn];44 45 ll farm() {46     int i;47     mf1(d);48     mz(f);49     f[0]=0;50     FOR(i,1,n) {51         if(d[a[i]]==-1) f[i]=(f[i-1] + f[i-1]+1)%MOD;52         else{53             f[i]=f[i-1] + f[i-1] - f[d[a[i]]-1];54             f[i]+=MMOD;55             f[i]%=MOD;56         }57         d[a[i]]=i;58     }59     return f[n];60 }61 62 int main() {63     //RE;64     //WE;65     int i;66     while(RD(n)!=EOF) {67         FOR(i,1,n)RD(a[i]);68         printf("%I64d\n",farm());69     }70 }

 1 import java.util.*; 2 import java.io.*; 3 import java.math.BigInteger; 4  5 public class Main { 6     public static final int MAXN = 333; 7     public static char[] s = null; 8     public static int N; 9     public static BigInteger[][] f = new BigInteger[MAXN][MAXN];10     public static final BigInteger F1 = BigInteger.valueOf(-1);11     public static final BigInteger ZERO = BigInteger.valueOf(0);12     public static final BigInteger ONE = BigInteger.valueOf(1);13 14     public static BigInteger gank(int last, int o) {15         // System.out.printf("Gank %d,%d\n",last,o);16         if (last >= 0 && !f[last][o].equals(F1))17             return f[last][o];18         BigInteger re = ZERO;19         if (o == 0)20             re = ONE;21         int i = last + 1;22         while (i < N && (s[i] != ‘(‘))23             i++;24         if (i < N)25             re = re.add(gank(i, o + 1));26         if (o > 0) {27             i = last + 1;28             while (i < N && (s[i] != ‘)‘))29                 i++;30             if (i < N)31                 re = re.add(gank(i, o - 1));32         }33         if (last >= 0)34             f[last][o] = re;35         return re;36     }37 38     public static void main(String[] args) throws Exception {39         File fin = new File("brackets.in");40         File fout = new File("brackets.out");41         InputStream ins = new FileInputStream(fin);42         OutputStream ous = new FileOutputStream(fout);43         Reader.init(ins);44         String S = Reader.next();45         s = S.toCharArray();46         N = S.length();47         for (int i = 0; i < MAXN; i++) {48             for (int j = 0; j < MAXN; j++) {49                 f[i][j] = F1;50             }51         }52         BigInteger ans = gank(-1, 0);53         ous.write(ans.toString().getBytes());54     }55 }56 57 class Reader {58     static BufferedReader reader;59     static StringTokenizer tokenizer;60 61     /** call this method to initialize reader for InputStream */62     static void init(InputStream input) {63         reader = new BufferedReader(new InputStreamReader(input));64         tokenizer = new StringTokenizer("");65     }66 67     /** get next word */68     static String next() throws IOException {69         while (!tokenizer.hasMoreTokens()) {70             // TODO add check for eof if necessary71             tokenizer = new StringTokenizer(reader.readLine());72         }73         return tokenizer.nextToken();74     }75 76     static int nextInt() throws IOException {77         return Integer.parseInt(next());78     }79 80     static double nextDouble() throws IOException {81         return Double.parseDouble(next());82     }83 }

  1 #include<cstdio>  2 #include<cmath>  3 #include<iostream>  4 #include<cstring>  5 #include<algorithm>  6 #include<cmath>  7 #include<map>  8 #include<set>  9 #include<stack> 10 #include<queue> 11 #include<cassert> 12 using namespace std; 13 #define mz(array) memset(array, 0, sizeof(array)) 14 #define mf1(array) memset(array, -1, sizeof(array)) 15 #define minf(array) memset(array, 0x3f, sizeof(array)) 16 #define REP(i,n) for(i=0;i<(n);i++) 17 #define FOR(i,x,n) for(i=(x);i<=(n);i++) 18 #define FORD(i,x,y) for(i=(x);i>=(y);i--) 19 #define RD(x) scanf("%d",&x) 20 #define RD2(x,y) scanf("%d%d",&x,&y) 21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 22 #define WN(x) printf("%d\n",x); 23 #define RE  freopen("knapsack.in","r",stdin) 24 #define WE  freopen("knapsack.out","w",stdout) 25 #define mp make_pair 26 #define pb push_back 27 #define pf push_front 28 #define ppf pop_front 29 #define ppb pop_back 30 typedef long long ll; 31 typedef unsigned long long ull; 32 typedef long double LD; 33   34 const int maxm=20011; 35 const int maxn=2011; 36   37 int dp[maxm], c[maxm], n, m, w[maxn], v[maxn]; 38 int d[maxn][maxm]; 39 vector<int> V; 40 int main() { 41     RE; 42     WE; 43 //    freopen("in.txt","r",stdin); 44     while(~scanf("%d%d", &n, &m)) { 45         memset(dp, 0 ,sizeof(dp)); 46         memset(c, -1, sizeof(c)); 47         mz(d); 48         assert(n>0&&n<=1000); 49         assert(m>0&&m<=10000); 50         for(int i=1; i<=n; i++) scanf("%d", &v[i]); 51         for(int i=1; i<=n; i++) scanf("%d", &w[i]); 52         for(int i=1;i<=n;i++){ 53                 assert(v[i]>=0&&v[i]<=100); 54                 assert(w[i]>=0&&w[i]<=100); 55                 //while(1); 56                 //return 0; 57   58         } 59         for(int i=1; i<=n; i++) { 60             for(int j=m; j>=v[i]; j--) { 61                 assert(j>=v[i]); 62                 if(dp[j] < dp[j - v[i]] + w[i]) { 63                     dp[j] = dp[j - v[i]] + w[i]; 64                     c[j] = i; 65                     d[i][j]=c[j-v[i]]; 66                 } 67             } 68         } 69         int tmp=0, mx = 0; 70         for(int i=m; i>0; i--) 71             if(dp[i] > mx) { 72                 mx = dp[i]; 73                 tmp = i; 74             } 75         V.clear(); 76         if(tmp==0){ 77             puts("0"); 78             continue; 79         } 80         V.pb(c[tmp]); 81         int i=d[c[tmp]][tmp]; 82   83         tmp-=v[c[tmp]]; 84         while(i > 0 && tmp>=0) { 85             V.pb(i); 86             int t=v[i]; 87             assert(tmp>=0&&tmp<=m); 88             i=d[i][tmp]; 89             tmp -= t; 90         } 91         int sz = V.size(); 92         printf("%d\n",sz); 93         sort(V.begin(),V.end()); 94         for(int i=0;i<sz;i++){ 95             printf("%d%c",V[i],i==sz-1?‘\n‘:‘ ‘); 96         } 97         //if(sz==0)puts(""); 98     } 99     return 0;100 }

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 #include<climits>13 using namespace std;14 #define mz(array) memset(array, 0, sizeof(array))15 #define mf1(array) memset(array, -1, sizeof(array))16 #define minf(array) memset(array, 0x3f, sizeof(array))17 #define REP(i,n) for(i=0;i<(n);i++)18 #define FOR(i,x,n) for(i=(x);i<=(n);i++)19 #define FORD(i,x,y) for(i=(x);i>=(y);i--)20 #define RD(x) scanf("%d",&x)21 #define RD2(x,y) scanf("%d%d",&x,&y)22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)23 #define WN(x) printf("%d\n",x);24 #define RE  freopen("dominoes.in","r",stdin)25 #define WE  freopen("dominoes.out","w",stdout)26 #define mp make_pair27 #define pb push_back28 #define pf push_front29 #define ppf pop_front30 #define ppb pop_back31 typedef long long ll;32 typedef unsigned long long ull;33 typedef long double LD;34 const ll MOD=1e9;35 int m,n;36  37 const int maxs=(1<<15)+10;38 const int maxn=111;39 int f[maxn][maxs];40  41 inline void dfs(const int &H, const int &s,const int &ss,const int &d){42     if(d==m){43         f[H][ss] += f[H-1][s];44         f[H][ss] %= MOD;45         return;46     }47     if(s&(1<<d))dfs(H,s,ss,d+1);48     else{49         dfs(H,s, ss|(1<<d) ,d+1);50         if(d<m-1 && ((s&(1<<(d+1)))==0))51             dfs(H, s, ss, d+2);52     }53 }54  55 inline int farm(){56     int i,j,k;57     int maxi=1<<m;58     mz(f);59     f[0][0]=1;60     FOR(i,1,n){61         REP(j,maxi)62             if(f[i-1][j]){63                 dfs(i,j,0,0);64             }65     }66     return f[n][0];67 }68  69 int main(){70     RE;71     WE;72     while(RD2(m,n)!=EOF){73         printf("%d\n",farm());74     }75     return 0;76 }

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define mz(array) memset(array, 0, sizeof(array))14 #define mf1(array) memset(array, -1, sizeof(array))15 #define minf(array) memset(array, 0x3f, sizeof(array))16 #define REP(i,n) for(i=0;i<(n);i++)17 #define FOR(i,x,n) for(i=(x);i<=(n);i++)18 #define FORD(i,x,y) for(i=(x);i>=(y);i--)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE  freopen("countpaths.in","r",stdin)24 #define WE  freopen("countpaths.out","w",stdout)25 #define mp make_pair26 #define pb push_back27 #define pf push_front28 #define ppf pop_front29 #define maxn 10000530 #define maxm 20000531 32 int head[maxn];33 int en;34 #define ll long long35 struct pp{36     int v,next;37 38 }e[maxm];39 void  add(int u,int v){40     e[en].v=v;41     e[en].next=head[u];42     head[u]=en++;43 }44 45 ll f[maxn];46 #define mod 100000000747 48 ll dfs(ll x){49     if(f[x]!=-1)return f[x];50     ll re=0;51     int i;52     for(i=head[x]; i!=-1; i=e[i].next){53         re+=dfs(e[i].v);54         re%=mod;55     }56     f[x]=re;57     return re;58 }59 60 int main(){61     int n,m;62     RE;63     WE;64     scanf("%d%d",&n,&m);65     memset(head,-1,sizeof(head));66     en=0;67     for(int i=0;i<m;i++){68         int a,b;69         scanf("%d%d",&a,&b);70         add(a,b);71     }72     memset(f,-1,sizeof(f));73     f[n]=1;74     cout<<dfs(1)<<endl;75 }

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define mz(array) memset(array, 0, sizeof(array))14 #define mf1(array) memset(array, -1, sizeof(array))15 #define minf(array) memset(array, 0x3f, sizeof(array))16 #define REP(i,n) for(i=0;i<(n);i++)17 #define FOR(i,x,n) for(i=(x);i<=(n);i++)18 #define FORD(i,x,y) for(i=(x);i>=(y);i--)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE  freopen("lcs.in","r",stdin)24 #define WE  freopen("lcs.out","w",stdout)25 #define mp make_pair26 #define pb push_back27 #define pf push_front28 #define ppf pop_front29 #define ppb pop_back30 typedef long long ll;31 typedef unsigned long long ull;32 typedef long double LD;33 34 const int maxn=2111;35 36 int n,m;37 int a[maxn];38 int b[maxn];39 40 int f[maxn][maxn];41 pair<int,int> pre[maxn][maxn];42 43 int ans;44 vector<int>an;45 46 void farm() {47     int i,j;48     mz(f);49     FOR(i,1,n) {50         FOR(j,1,m) {51             if(a[i]==b[j]) {52                 f[i][j]=f[i-1][j-1] + 1;53                 pre[i][j]=mp(i-1,j-1);54             } else {55                 if(f[i-1][j]>f[i][j-1])f[i][j]=f[i-1][j] , pre[i][j]=mp(i-1,j);56                 else f[i][j]=f[i][j-1] , pre[i][j]=mp(i,j-1);57             }58         }59     }60     ans=f[n][m];61     i=n,j=m;62     an.clear();63     while(f[i][j]!=0){64         int qi=pre[i][j].first;65         int qj=pre[i][j].second;66         if(f[i][j]>f[qi][qj])an.pb(a[i]);67         i=qi,j=qj;68     }69 }70 71 int main() {72     RE;73     WE;74     int i;75     while(RD(n)!=EOF) {76         FOR(i,1,n)RD(a[i]);77         RD(m);78         FOR(i,1,m)RD(b[i]);79         farm();80         printf("%d\n",ans);81         if(ans>0)printf("%d",an[ans-1]);82         FORD(i,ans-2,0){83             printf(" %d",an[i]);84         }85         puts("");86     }87     return 0;88 }

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define mz(array) memset(array, 0, sizeof(array))14 #define mf1(array) memset(array, -1, sizeof(array))15 #define minf(array) memset(array, 0x3f, sizeof(array))16 #define REP(i,n) for(i=0;i<(n);i++)17 #define FOR(i,x,n) for(i=(x);i<=(n);i++)18 #define FORD(i,x,y) for(i=(x);i>=(y);i--)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE  freopen("levenshtein.in","r",stdin)24 #define WE  freopen("levenshtein.out","w",stdout)25 #define mp make_pair26 #define pb push_back27 #define pf push_front28 #define ppf pop_front29 #define ppb pop_back30 31 //#define inf 0x7fffffff32 //char a[5005],b[5005];33 //int dp[5005][5005];34 //int main(){35 //    while(scanf("%s%s",a,b)==2){36 //        int len1=strlen(a);37 //        int len2=strlen(b);38 //        for(int i=0;i<=len1;i++)39 //            for(int j=0;j<=len2;j++)dp[i][j]=inf;40 //        for(int i=0;i<=len1;i++)dp[0][i]=i;41 //        for(int i=0;i<=len2;i++)dp[i][0]=i;42 //        for(int i=1;i<=len1;i++){43 //            for(int j=1;j<=len2;j++){44 //                dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+(b[i]==a[j])?0:1));45 //            }46 //        }47 //        cout<<dp[len1][len2]<<endl;48 //    }49 //    return 0;50 //}51 //52 53 char s1[6000],s2[6000];54 int d[6000][6000];55 int min(int a,int b,int c) {56     int t = a < b ? a : b;57     return t < c ? t : c;58 }59 void editDistance(int len1,int len2)60 {61     int i,j;62     for(i = 0;i <= len1;i++)63         d[i][0] = i;64     for(j = 0;j <= len2;j++)65         d[0][j] = j;66     for(i = 1;i <= len1;i++)67         for(j = 1;j <= len2;j++)68         {69             int cost = s1[i-1] == s2[j-1] ? 0 : 1;70             int deletion = d[i-1][j] + 1;71             int insertion = d[i][j-1] + 1;72             int substitution = d[i-1][j-1] + cost;73             d[i][j] = min(deletion,insertion,substitution);74         }75         printf("%d\n",d[len1][len2]);76 }77 int main()78 {79     RE;80     WE;81     while(scanf("%s %s",s1,s2) != EOF)82         editDistance(strlen(s1),strlen(s2));83         return 0;84 }

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define mz(array) memset(array, 0, sizeof(array))14 #define mf1(array) memset(array, -1, sizeof(array))15 #define minf(array) memset(array, 0x3f, sizeof(array))16 #define REP(i,n) for(i=0;i<(n);i++)17 #define FOR(i,x,n) for(i=(x);i<=(n);i++)18 #define FORD(i,x,y) for(i=(x);i>=(y);i--)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE  freopen("lis.in","r",stdin)24 #define WE  freopen("lis.out","w",stdout)25 #define mp make_pair26 #define pb push_back27 #define pf push_front28 #define ppf pop_front29 #define ppb pop_back30 typedef long long ll;31 typedef unsigned long long ull;32 typedef long double LD;33 34 const int maxn=5555;35 36 int n;37 int a[maxn];38 39 int f[maxn];40 int pre[maxn];41 42 int ans;43 vector<int>an;44 45 inline void farm() {46     int i,j;47     mz(pre);48     FOR(i,1,n) {49         f[i]=1;50         FOR(j,1,i-1) {51             if(a[i]>a[j] && f[j]+1>f[i]) {52                 f[i]=f[j]+1;53                 pre[i]=j;54             }55         }56     }57     ans=0;58     int ai=0;59     FOR(i,1,n) {60         if(f[i]>ans)ans=f[i], ai=i;61     }62     i=ai;63     an.clear();64     REP(j,ans) {65         an.pb(a[i]);66         i=pre[i];67     }68 }69 70 int main() {71     RE;72     WE;73     int i;74     while(RD(n)!=EOF) {75         if(n>=maxn)while(1);76         FOR(i,1,n)RD(a[i]);77         farm();78         printf("%d\n",ans);79         if(ans>0)printf("%d",an[ans-1]);80         FORD(i,ans-2,0) {81             printf(" %d",an[i]);82         }83         puts("");84     }85     return 0;86 }

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 #include<climits>13 using namespace std;14 #define mz(array) memset(array, 0, sizeof(array))15 #define mf1(array) memset(array, -1, sizeof(array))16 #define minf(array) memset(array, 0x3f, sizeof(array))17 #define REP(i,n) for(i=0;i<(n);i++)18 #define FOR(i,x,n) for(i=(x);i<=(n);i++)19 #define FORD(i,x,y) for(i=(x);i>=(y);i--)20 #define RD(x) scanf("%d",&x)21 #define RD2(x,y) scanf("%d%d",&x,&y)22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)23 #define WN(x) printf("%d\n",x);24 #define RE  freopen("matrix.in","r",stdin)25 #define WE  freopen("matrix.out","w",stdout)26 #define mp make_pair27 #define pb push_back28 #define pf push_front29 #define ppf pop_front30 #define ppb pop_back31 typedef long long ll;32 typedef unsigned long long ull;33 typedef long double LD;34 35 const int maxn=1000 + 10;36 37 int n, a[maxn], b[maxn], m[maxn][maxn], s[maxn][maxn];38 void Print(int l ,int r){39     if(l == r){40         putchar(‘A‘);41         return;42     }43     putchar(‘(‘);44     Print(l, s[l][r]);45     Print(s[l][r] + 1, r);46     putchar(‘)‘);47 }48 int main(){49     RE;50     WE;51     scanf("%d", &n);52     for(int i=1; i<=n; i++) scanf("%d%d", &a[i], &b[i]), m[i][i] = 0;53     for(int l=2; l<=n; l++){54         for(int i=1; i<=n-l+1; i++){55             int j = i + l -1;56             m[i][j] = INT_MAX;57             for(int k=i; k<j; k++){58                 int q = m[i][k] + m[k + 1][j] + a[i] * b[k] * b[j];59                 if(q < m[i][j]){60                     m[i][j] = q;61                     s[i][j] = k;62                 }63             }64         }65     }66 //    cout << m[1][n] << endl;67     Print(1, n);68     return 0;69 }

  1 //#pragma comment(linker, "/STACK:102400000,102400000")  2 #include<cstdio>  3 #include<cmath>  4 #include<iostream>  5 #include<cstring>  6 #include<algorithm>  7 #include<cmath>  8 #include<map>  9 #include<set> 10 #include<stack> 11 #include<queue> 12 #include<climits> 13 using namespace std; 14 #define mz(array) memset(array, 0, sizeof(array)) 15 #define mf1(array) memset(array, -1, sizeof(array)) 16 #define minf(array) memset(array, 0x3f, sizeof(array)) 17 #define REP(i,n) for(i=0;i<(n);i++) 18 #define FOR(i,x,n) for(i=(x);i<=(n);i++) 19 #define FORD(i,x,y) for(i=(x);i>=(y);i--) 20 #define RD(x) scanf("%d",&x) 21 #define RD2(x,y) scanf("%d%d",&x,&y) 22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 23 #define WN(x) printf("%d\n",x); 24 #define RE  freopen("palindrome.in","r",stdin) 25 #define WE  freopen("palindrome.out","w",stdout) 26 #define mp make_pair 27 #define pb push_back 28 #define pf push_front 29 #define ppf pop_front 30 #define ppb pop_back 31 typedef long long ll; 32 typedef unsigned long long ull; 33 typedef long double LD; 34  35 const int maxn=2222; 36  37 char s[2222]; 38 int f[2222][2222]; 39 pair<int,int> pre[maxn][maxn]; 40  41 int ans; 42 vector<char>anl,anr; 43  44 void farm(){ 45     int len=strlen(s); 46     int i,j,k; 47     mz(f); 48     mf1(pre); 49     REP(i,len)f[i][i]=1 , pre[i][i]=mp(-1,-1); 50     FOR(k,1,len-1){ 51         FOR(i,0,len-2){ 52             j=i+k; 53             if(j>len-1)break; 54             if(s[i]==s[j]){ 55                 if(j-i>1){ 56                     f[i][j]=f[i+1][j-1]+2; 57                     pre[i][j] = mp(i+1,j-1); 58                 }else{ 59                     f[i][j]=2; 60                     pre[i][j]=mp(-1,-1); 61                 } 62             }else{ 63                 if(f[i][j-1] > f[i+1][j])f[i][j]=f[i][j-1] , pre[i][j]=mp(i,j-1); 64                 else f[i][j]=f[i+1][j] , pre[i][j]=mp(i+1,j); 65             } 66         } 67     } 68     ans=f[0][len-1]; 69     i=0; 70     j=len-1; 71     anl.clear(); 72     anr.clear(); 73     int qi,qj; 74     while(i>=0 && j>=0){ 75         qi=pre[i][j].first; 76         qj=pre[i][j].second; 77         if(qi<0 || qj<0){ 78             if(f[i][j]!=0){ 79                 if(i==j)anl.pb(s[i]); 80                 else anl.pb(s[i]),anr.pb(s[i]); 81             } 82             break; 83         } 84         //printf("%d,%d %d,%d %d,%d\n",i,j,qi,qj,f[i][j] , f[qi][qj]); 85         if(f[i][j] > f[qi][qj]){ 86             if(i!=j)anl.pb(s[i]), anr.pb(s[i]); 87             else anl.pb(s[i]); 88             //printf("%d,%c\n",i!=j,s[i]); 89         } 90         i=qi; 91         j=qj; 92     } 93 } 94  95 int main(){ 96     int i; 97     RE; 98     WE; 99     while(scanf("%s",s)!=EOF){100         farm();101         printf("%d\n",ans);102         REP(i,anl.size())putchar(anl[i]);103         FORD(i,anr.size()-1,0)putchar(anr[i]);104         puts("");105     }106 }