今天练了一波DP。时间紧迫我就只贴代码了。

20141120

fzu2129

http://acm.fzu.edu.cn/problem.php?pid=2129

不同的子序列个数

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("brackets.in","r",stdin)

 #define WE  freopen("brackets.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define ppb pop_back

 typedef long long ll;

 typedef unsigned long long ull;

 const double pi=acos(-1.0);

 const double eps=1e-;

 const ll MOD=1e9+;

 ll MMOD = MOD*;

 const int maxn=;

 int a[maxn];

 int n;

 ll f[maxn];

 int d[maxn];

 ll farm() {

     int i;

     mf1(d);

     mz(f);

     f[]=;

     FOR(i,,n) {

         if(d[a[i]]==-) f[i]=(f[i-] + f[i-]+)%MOD;

         else{

             f[i]=f[i-] + f[i-] - f[d[a[i]]-];

             f[i]+=MMOD;

             f[i]%=MOD;

         }

         d[a[i]]=i;

     }

     return f[n];

 }

 int main() {

     //RE;

     //WE;

     int i;

     while(RD(n)!=EOF) {

         FOR(i,,n)RD(a[i]);

         printf("%I64d\n",farm());

     }

 }

ASC17 A题

Brackets Subsequences

http://codeforces.com/gym/100221

不同的括号子序列个数，要用java的BigInteger。

 import java.util.*;

 import java.io.*;

 import java.math.BigInteger;

 public class Main {

     public static final int MAXN = 333;

     public static char[] s = null;

     public static int N;

     public static BigInteger[][] f = new BigInteger[MAXN][MAXN];

     public static final BigInteger F1 = BigInteger.valueOf(-1);

     public static final BigInteger ZERO = BigInteger.valueOf(0);

     public static final BigInteger ONE = BigInteger.valueOf(1);

     public static BigInteger gank(int last, int o) {

         // System.out.printf("Gank %d,%d\n",last,o);

         if (last >= 0 && !f[last][o].equals(F1))

             return f[last][o];

         BigInteger re = ZERO;

         if (o == 0)

             re = ONE;

         int i = last + 1;

         while (i < N && (s[i] != '('))

             i++;

         if (i < N)

             re = re.add(gank(i, o + 1));

         if (o > 0) {

             i = last + 1;

             while (i < N && (s[i] != ')'))

                 i++;

             if (i < N)

                 re = re.add(gank(i, o - 1));

         }

         if (last >= 0)

             f[last][o] = re;

         return re;

     }

     public static void main(String[] args) throws Exception {

         File fin = new File("brackets.in");

         File fout = new File("brackets.out");

         InputStream ins = new FileInputStream(fin);

         OutputStream ous = new FileOutputStream(fout);

         Reader.init(ins);

         String S = Reader.next();

         s = S.toCharArray();

         N = S.length();

         for (int i = 0; i < MAXN; i++) {

             for (int j = 0; j < MAXN; j++) {

                 f[i][j] = F1;

             }

         }

         BigInteger ans = gank(-1, 0);

         ous.write(ans.toString().getBytes());

     }

 }

 class Reader {

     static BufferedReader reader;

     static StringTokenizer tokenizer;

     /** call this method to initialize reader for InputStream */

     static void init(InputStream input) {

         reader = new BufferedReader(new InputStreamReader(input));

         tokenizer = new StringTokenizer("");

     }

     /** get next word */

     static String next() throws IOException {

         while (!tokenizer.hasMoreTokens()) {

             // TODO add check for eof if necessary

             tokenizer = new StringTokenizer(reader.readLine());

         }

         return tokenizer.nextToken();

     }

     static int nextInt() throws IOException {

         return Integer.parseInt(next());

     }

     static double nextDouble() throws IOException {

         return Double.parseDouble(next());

     }

 }

Knapsack

带路径输出的背包，感觉直接用二维数组会好一点，这个有点乱。

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 #include<cassert>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define FORD(i,x,y) for(i=(x);i>=(y);i--)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("knapsack.in","r",stdin)

 #define WE  freopen("knapsack.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define ppb pop_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef long double LD;

 const int maxm=;

 const int maxn=;

 int dp[maxm], c[maxm], n, m, w[maxn], v[maxn];

 int d[maxn][maxm];

 vector<int> V;

 int main() {

     RE;

     WE;

 //    freopen("in.txt","r",stdin);

     while(~scanf("%d%d", &n, &m)) {

         memset(dp,  ,sizeof(dp));

         memset(c, -, sizeof(c));

         mz(d);

         assert(n>&&n<=);

         assert(m>&&m<=);

         for(int i=; i<=n; i++) scanf("%d", &v[i]);

         for(int i=; i<=n; i++) scanf("%d", &w[i]);

         for(int i=;i<=n;i++){

                 assert(v[i]>=&&v[i]<=);

                 assert(w[i]>=&&w[i]<=);

                 //while(1);

                 //return 0;

         }

         for(int i=; i<=n; i++) {

             for(int j=m; j>=v[i]; j--) {

                 assert(j>=v[i]);

                 if(dp[j] < dp[j - v[i]] + w[i]) {

                     dp[j] = dp[j - v[i]] + w[i];

                     c[j] = i;

                     d[i][j]=c[j-v[i]];

                 }

             }

         }

         int tmp=, mx = ;

         for(int i=m; i>; i--)

             if(dp[i] > mx) {

                 mx = dp[i];

                 tmp = i;

             }

         V.clear();

         if(tmp==){

             puts("");

             continue;

         }

         V.pb(c[tmp]);

         int i=d[c[tmp]][tmp];

         tmp-=v[c[tmp]];

         while(i >  && tmp>=) {

             V.pb(i);

             int t=v[i];

             assert(tmp>=&&tmp<=m);

             i=d[i][tmp];

             tmp -= t;

         }

         int sz = V.size();

         printf("%d\n",sz);

         sort(V.begin(),V.end());

         for(int i=;i<sz;i++){

             printf("%d%c",V[i],i==sz-?'\n':' ');

         }

         //if(sz==0)puts("");

     }

     return ;

 }

Dominoes

15*100的1*2铺砖

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 #include<climits>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define FORD(i,x,y) for(i=(x);i>=(y);i--)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("dominoes.in","r",stdin)

 #define WE  freopen("dominoes.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define ppb pop_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef long double LD;

 const ll MOD=1e9;

 int m,n;

 const int maxs=(<<)+;

 const int maxn=;

 int f[maxn][maxs];

 inline void dfs(const int &H, const int &s,const int &ss,const int &d){

     if(d==m){

         f[H][ss] += f[H-][s];

         f[H][ss] %= MOD;

         return;

     }

     if(s&(<<d))dfs(H,s,ss,d+);

     else{

         dfs(H,s, ss|(<<d) ,d+);

         if(d<m- && ((s&(<<(d+)))==))

             dfs(H, s, ss, d+);

     }

 }

 inline int farm(){

     int i,j,k;

     int maxi=<<m;

     mz(f);

     f[][]=;

     FOR(i,,n){

         REP(j,maxi)

             if(f[i-][j]){

                 dfs(i,j,,);

             }

     }

     return f[n][];

 }

 int main(){

     RE;

     WE;

     while(RD2(m,n)!=EOF){

         printf("%d\n",farm());

     }

     return ;

 }

Number of paths in acyclic graph

有向无环图判1~n的路径数。

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define FORD(i,x,y) for(i=(x);i>=(y);i--)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("countpaths.in","r",stdin)

 #define WE  freopen("countpaths.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define maxn 100005

 #define maxm 200005

 int head[maxn];

 int en;

 #define ll long long

 struct pp{

     int v,next;

 }e[maxm];

 void  add(int u,int v){

     e[en].v=v;

     e[en].next=head[u];

     head[u]=en++;

 }

 ll f[maxn];

 #define mod 1000000007

 ll dfs(ll x){

     if(f[x]!=-)return f[x];

     ll re=;

     int i;

     for(i=head[x]; i!=-; i=e[i].next){

         re+=dfs(e[i].v);

         re%=mod;

     }

     f[x]=re;

     return re;

 }

 int main(){

     int n,m;

     RE;

     WE;

     scanf("%d%d",&n,&m);

     memset(head,-,sizeof(head));

     en=;

     for(int i=;i<m;i++){

         int a,b;

         scanf("%d%d",&a,&b);

         add(a,b);

     }

     memset(f,-,sizeof(f));

     f[n]=;

     cout<<dfs()<<endl;

 }

Longest common subsequence

LCS带路径输出

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define FORD(i,x,y) for(i=(x);i>=(y);i--)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("lcs.in","r",stdin)

 #define WE  freopen("lcs.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define ppb pop_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef long double LD;

 const int maxn=;

 int n,m;

 int a[maxn];

 int b[maxn];

 int f[maxn][maxn];

 pair<int,int> pre[maxn][maxn];

 int ans;

 vector<int>an;

 void farm() {

     int i,j;

     mz(f);

     FOR(i,,n) {

         FOR(j,,m) {

             if(a[i]==b[j]) {

                 f[i][j]=f[i-][j-] + ;

                 pre[i][j]=mp(i-,j-);

             } else {

                 if(f[i-][j]>f[i][j-])f[i][j]=f[i-][j] , pre[i][j]=mp(i-,j);

                 else f[i][j]=f[i][j-] , pre[i][j]=mp(i,j-);

             }

         }

     }

     ans=f[n][m];

     i=n,j=m;

     an.clear();

     while(f[i][j]!=){

         int qi=pre[i][j].first;

         int qj=pre[i][j].second;

         if(f[i][j]>f[qi][qj])an.pb(a[i]);

         i=qi,j=qj;

     }

 }

 int main() {

     RE;

     WE;

     int i;

     while(RD(n)!=EOF) {

         FOR(i,,n)RD(a[i]);

         RD(m);

         FOR(i,,m)RD(b[i]);

         farm();

         printf("%d\n",ans);

         if(ans>)printf("%d",an[ans-]);

         FORD(i,ans-,){

             printf(" %d",an[i]);

         }

         puts("");

     }

     return ;

 }

Levenshtein distance

编辑距离？队友写的，日后我再看看。

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define FORD(i,x,y) for(i=(x);i>=(y);i--)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("levenshtein.in","r",stdin)

 #define WE  freopen("levenshtein.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define ppb pop_back

 //#define inf 0x7fffffff

 //char a[5005],b[5005];

 //int dp[5005][5005];

 //int main(){

 //    while(scanf("%s%s",a,b)==2){

 //        int len1=strlen(a);

 //        int len2=strlen(b);

 //        for(int i=0;i<=len1;i++)

 //            for(int j=0;j<=len2;j++)dp[i][j]=inf;

 //        for(int i=0;i<=len1;i++)dp[0][i]=i;

 //        for(int i=0;i<=len2;i++)dp[i][0]=i;

 //        for(int i=1;i<=len1;i++){

 //            for(int j=1;j<=len2;j++){

 //                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));

 //            }

 //        }

 //        cout<<dp[len1][len2]<<endl;

 //    }

 //    return 0;

 //}

 //

 char s1[],s2[];

 int d[][];

 int min(int a,int b,int c) {

     int t = a < b ? a : b;

     return t < c ? t : c;

 }

 void editDistance(int len1,int len2)

 {

     int i,j;

     for(i = ;i <= len1;i++)

         d[i][] = i;

     for(j = ;j <= len2;j++)

         d[][j] = j;

     for(i = ;i <= len1;i++)

         for(j = ;j <= len2;j++)

         {

             int cost = s1[i-] == s2[j-] ?  : ;

             int deletion = d[i-][j] + ;

             int insertion = d[i][j-] + ;

             int substitution = d[i-][j-] + cost;

             d[i][j] = min(deletion,insertion,substitution);

         }

         printf("%d\n",d[len1][len2]);

 }

 int main()

 {

     RE;

     WE;

     while(scanf("%s %s",s1,s2) != EOF)

         editDistance(strlen(s1),strlen(s2));

         return ;

 }

Longest increasing subsequence

LIS，带路径输出

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define FORD(i,x,y) for(i=(x);i>=(y);i--)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("lis.in","r",stdin)

 #define WE  freopen("lis.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define ppb pop_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef long double LD;

 const int maxn=;

 int n;

 int a[maxn];

 int f[maxn];

 int pre[maxn];

 int ans;

 vector<int>an;

 inline void farm() {

     int i,j;

     mz(pre);

     FOR(i,,n) {

         f[i]=;

         FOR(j,,i-) {

             if(a[i]>a[j] && f[j]+>f[i]) {

                 f[i]=f[j]+;

                 pre[i]=j;

             }

         }

     }

     ans=;

     int ai=;

     FOR(i,,n) {

         if(f[i]>ans)ans=f[i], ai=i;

     }

     i=ai;

     an.clear();

     REP(j,ans) {

         an.pb(a[i]);

         i=pre[i];

     }

 }

 int main() {

     RE;

     WE;

     int i;

     while(RD(n)!=EOF) {

         if(n>=maxn)while();

         FOR(i,,n)RD(a[i]);

         farm();

         printf("%d\n",ans);

         if(ans>)printf("%d",an[ans-]);

         FORD(i,ans-,) {

             printf(" %d",an[i]);

         }

         puts("");

     }

     return ;

 }

Maximal weight matching in tree

树上选一些边，没有公共顶点，要求边权和最大。

树DP，队友写的。

哇，代码不见啦！反正就是f[i][j],j=0~1,0是不用这个点，1是用这个点。

Matrix multiplication

矩阵链乘，加括号使得代价最小，带路径输出。算法导论题，队友写的，碉

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 #include<climits>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define FORD(i,x,y) for(i=(x);i>=(y);i--)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("matrix.in","r",stdin)

 #define WE  freopen("matrix.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define ppb pop_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef long double LD;

 const int maxn= + ;

 int n, a[maxn], b[maxn], m[maxn][maxn], s[maxn][maxn];

 void Print(int l ,int r){

     if(l == r){

         putchar('A');

         return;

     }

     putchar('(');

     Print(l, s[l][r]);

     Print(s[l][r] + , r);

     putchar(')');

 }

 int main(){

     RE;

     WE;

     scanf("%d", &n);

     for(int i=; i<=n; i++) scanf("%d%d", &a[i], &b[i]), m[i][i] = ;

     for(int l=; l<=n; l++){

         for(int i=; i<=n-l+; i++){

             int j = i + l -;

             m[i][j] = INT_MAX;

             for(int k=i; k<j; k++){

                 int q = m[i][k] + m[k + ][j] + a[i] * b[k] * b[j];

                 if(q < m[i][j]){

                     m[i][j] = q;

                     s[i][j] = k;

                 }

             }

         }

     }

 //    cout << m[1][n] << endl;

     Print(, n);

     return ;

 }

Longest subpalindrome

最长回文子串，带路径输出。

f[l][r]记录区间[l,r]的最长回文子串长度，区间从小到大搞。

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 #include<climits>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define FORD(i,x,y) for(i=(x);i>=(y);i--)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("palindrome.in","r",stdin)

 #define WE  freopen("palindrome.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define ppb pop_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef long double LD;

 const int maxn=;

 char s[];

 int f[][];

 pair<int,int> pre[maxn][maxn];

 int ans;

 vector<char>anl,anr;

 void farm(){

     int len=strlen(s);

     int i,j,k;

     mz(f);

     mf1(pre);

     REP(i,len)f[i][i]= , pre[i][i]=mp(-,-);

     FOR(k,,len-){

         FOR(i,,len-){

             j=i+k;

             if(j>len-)break;

             if(s[i]==s[j]){

                 if(j-i>){

                     f[i][j]=f[i+][j-]+;

                     pre[i][j] = mp(i+,j-);

                 }else{

                     f[i][j]=;

                     pre[i][j]=mp(-,-);

                 }

             }else{

                 if(f[i][j-] > f[i+][j])f[i][j]=f[i][j-] , pre[i][j]=mp(i,j-);

                 else f[i][j]=f[i+][j] , pre[i][j]=mp(i+,j);

             }

         }

     }

     ans=f[][len-];

     i=;

     j=len-;

     anl.clear();

     anr.clear();

     int qi,qj;

     while(i>= && j>=){

         qi=pre[i][j].first;

         qj=pre[i][j].second;

         if(qi< || qj<){

             if(f[i][j]!=){

                 if(i==j)anl.pb(s[i]);

                 else anl.pb(s[i]),anr.pb(s[i]);

             }

             break;

         }

         //printf("%d,%d %d,%d %d,%d\n",i,j,qi,qj,f[i][j] , f[qi][qj]);

         if(f[i][j] > f[qi][qj]){

             if(i!=j)anl.pb(s[i]), anr.pb(s[i]);

             else anl.pb(s[i]);

             //printf("%d,%c\n",i!=j,s[i]);

         }

         i=qi;

         j=qj;

     }

 }

 int main(){

     int i;

     RE;

     WE;

     while(scanf("%s",s)!=EOF){

         farm();

         printf("%d\n",ans);

         REP(i,anl.size())putchar(anl[i]);

         FORD(i,anr.size()-,)putchar(anr[i]);

         puts("");

     }

 }

Travelling salesman problem

旅行商问题，代码不见了。

f[i][j]，一个是状压的到过哪个地方的状态，另一个是最后在哪个点。

String Decomposition

把字符串弄成又几个子串增殖出来的

太难啦，还没做出来

Solid Tilings

另一种比较难的铺砖，还没看。

最新文章

  1. Linux程序包管理之yum及源代码安装
  2. Day10-线程进程
  3. Java_类的热替换
  4. char、varchar、text和nchar、nvarchar、ntext的区别
  5. 枚举PEB获取进程模块列表
  6. 配置FastDFS
  7. 找工作--Java相关
  8. Mac下运行ASP.NET Core应用程序
  9. Wpf 数据绑定之BindingBase.StringFormat
  10. mongodb3.0 性能測试报告 一
  11. Lrc歌词批量下载助手 MP3歌词批量下载助手
  12. Dijkstra算法求单源最短路径
  13. News feed
  14. JVM查找类文件的顺序(转)
  15. WCF（一）基础整理
  16. Java代码操作SVN
  17. BeanFactory not initialized or already closed - call &#39;refresh&#39; before accessing beans via the ApplicationContext
  18. oracle手工生成AWR报告方法记录
  19. UIView的绘制原理
  20. AutoCAD 2019.0.1 Update 官方简体中文版

热门文章

  1. Centos7中所有的关机命令的奇怪现象
  2. 理解 OpenStack + Ceph （9）： Ceph 的size/min_size/choose/chooseleaf/scrubbing/repair 等概念
  3. Java常见问题
  4. 关于css的一些事情（1）
  5. java进程占用CPU资源过高分析脚本
  6. 【CSS】创建布局
  7. 第1章Java入门体验
  8. 关于SSH的一些tricks
  9. ireport制作小技巧&lt;Reproduce&gt;
  10. （原创）JAVA多线程一传统多线程