简单Dp----最长公共子序列，DAG最长路，简单区间DP等

时间：2021-12-09 16:26:09
/*
　　uva 111

 * 题意：

 *        顺序有变化的最长公共子序列；

 *        模板；

 */

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int a[];

int mu[];

int Dp[][];

int main()

{

    int n,x;

    scanf("%d", &n);

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

    {

        scanf("%d", &x);

        mu[x] = i;

    }

    while(scanf("%d", &x)!=EOF)

    {

        a[x] = ;

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

        {

            scanf("%d", &x);

            a[x] = i;

        }

        memset(Dp,, sizeof(Dp) );

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

        {

            for(int j=;j<=n;j++)

            {

                if(a[i] == mu[j])

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

                else

                    Dp[i][j] = max(Dp[i-][j], Dp[i][j-]);

            }

        }

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

    }

    return ;

}
/*

 * uva103

 * 题意：

 *        DAG最长路；

 */

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int cube[][];

int G[][];

int Dp[];

int pre[];

int n,di;

void Dfs(int u)

{

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

    {

        if(i==u)

            continue;

        if( G[u][i]!= - )

        {

            if(Dp[i] < Dp[u]+G[u][i])

            {

                Dp[i] = Dp[u] + G[u][i];

                pre[i] = u;

                Dfs(i);

            }

        }

    }

}

void print(int u)

{

    if(pre[u]!=-)

        print(pre[u]);

    if(pre[u]!= -)

        printf(" ");

    printf("%d", u);

}

int main()

{

    while(scanf("%d%d", &n,&di)!=EOF)

    {

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

            for(int j=; j<di; j++)

                scanf("%d", &cube[i][j]);

        memset(G, -, sizeof(G));

        memset(pre, -, sizeof(pre));

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

            sort(cube[i],cube[i]+di);

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

            for(int j=;j<=n;j++)

            {

                if(i==j)

                    continue;

                int flag = ;

                for(int x =;x<di;x++)

                    if( cube[i][x] >= cube[j][x])

                    {

                        flag = ;

                        break;

                    }

                if( !flag )

                    G[i][j] = ;

            }

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

            Dp[i] = ;

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

            Dfs(i);

        int ans =;

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

        {

            if(Dp[ans] < Dp[i])

                ans  =i;

        }

        printf("%d\n", Dp[ans]);

        print(ans);

        printf("\n");

    }

    return ;

}
/*

 * uva10405

 * 题意：

 *        LCS；

 */

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n1, n2;

char s1[],s2[];

int Dp[][];

int LCS()

{

    memset(Dp, , sizeof(Dp));

    for(int i=;i<=n1; i++)

        for(int j=; j<=n2; j++)

            if( s1[i] == s2[j] )

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

            else

                Dp[i][j] = max(Dp[i-][j], Dp[i][j-]);

    return Dp[n1][n2];

}

int main()

{

    while(gets(s1+)&& gets(s2+))

    {

        n1 = strlen(s1+);

        n2 = strlen(s2+);

        int ans = LCS();

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

    }

    return ;

}
/*

 * uva10003

 * 区间Dp

 * 题意，给一个序列是要切开的位置，每次切一刀的代价是当前段的全长；

 * 最小代价；

 * 在区间开始和结尾加上0 和全长；

 * 枚举区间 长度、起点；

 * 这里的长度是跨越的要切的位置的个数，不是真正的长度；

 * 对于每一段内，枚举段内分割点，然后Dp出段内最小代价，直到全长；

 */

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int a[],len,n;

int Dp[][];

int INF = 0x3f3f3f3f;

int main()

{

    while(scanf("%d", &len )!=EOF && len )

    {

        memset(Dp, , sizeof(Dp));

        scanf("%d", &n);

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

            scanf("%d", &a[i]);

        a[] = ;

        a[n+] = len;

        //区间Dp

        //Dp[i][j]表示左闭右开的区间i，j;

        for(int p = ; p <= n+ ; p++)

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

            {

                int j = i+p;

                int Min = INF;

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

                    Min = min(Min, Dp[i][k]+Dp[k][j]+a[j]-a[i]);

                if( Min != INF )

                    Dp[i][j] = Min;

            }

        printf("The minimum cutting is %d.\n",Dp[][n+]);

    }

    return ;

}
/*

 * uva116

 * 简单的Dp，前缀最小要倒着DP

 */

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m;

int a[][];

int Dp[][];

int Next[][];

void print(int i,int j)

{

    if(j<=)

        return ;

    print(Next[i][j], j-);

    if(j>)

        printf(" ");

    printf("%d",Next[i][j]);

}

int main()

{

    while(scanf("%d%d", &n, &m)!=EOF)

    {

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

            for(int j = ;j<=m;j++)

                scanf("%d", &a[i][j]);

        memset(Dp, 0x3f, sizeof(Dp));

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

            Dp[i][m] = a[i][m];

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

        {

            for(int j=;j<=n;j++)

            {

                int s[]={j-,j,j+};

                if(j-==) s[] = n;

                if(j+>n) s[] = ;

                sort(s,s+);

                int t = s[];

                Dp[j][i] = Dp[t][i+] + a[j][i];

                Next[j][i] = t;

                t = s[] ;

                if(Dp[j][i] > Dp[t][i+] + a[j][i])

                {

                    Dp[j][i] = Dp[t][i+] + a[j][i];

                    Next[j][i] = t;

                }

                t = s[] ;

                if(Dp[j][i] > Dp[t][i+]+a[j][i])

                {

                    Dp[j][i] = Dp[t][i+] + a[j][i];

                    Next[j][i] = t;

                }

            }

        }

        int ans =;

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

            if(Dp[ans][] > Dp[i][])

                ans = i;

    //    print(ans,m);

        printf("%d",ans);

        int x =ans, y=;

        while(y<m)

        {

            printf(" %d", Next[x][y]);

            x = Next[x][y];

            y++;

        }

        printf("\n%d\n",Dp[ans][]);

    }

    return ;

}
/*

 * uva562

 * 给一列数，分成两堆，两堆的差最小；

 * 0-1背包处理出所有可能的和；

 * 然后从一半开始往下扫；

 */

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int a[];

int Dp[];

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int n;

        scanf("%d", &n);

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

            scanf("%d", &a[i]);

        int sum = ;

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

            sum += a[i];

        memset(Dp, , sizeof(Dp));

        Dp[] = ;

        for(int j=; j<n;j++)

            for(int i= sum; i>=a[j]; i--)

                if(!Dp[i]) Dp[i] = Dp[i-a[j]];

        for(int i=sum/;i>=;i--)

            if(Dp[i])

            {

                printf("%d\n",sum-i-i);

                break;

            }

    }

    return ;

}
/*************************************************************************

 > File Name: uva348.cpp

 > Author: Baiyan

 > 题意：给一列矩阵的尺寸，问怎么样的计算顺序会使计算的次数最少

 >

 > Created Time: 2016年04月19日 星期二 22时52分37秒

 **********************************************************************/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

int a[],b[];

int Dp[][];

int vis[][];

void print(int l,int r)

{

    if(r-l>)

    {

        printf("(");

        print(l,vis[l][r]);

        printf(" x ");

        print(vis[l][r]+,r);

        printf(")");

    }

    else

        printf("A%d",l);

}

int main()

{

    int n,k=;

    while(scanf("%d", &n)!=EOF && n)

    {

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

            scanf("%d%d", &a[i], &b[i]);

        memset(Dp, , sizeof(Dp));

        memset(vis,, sizeof(vis));

        for(int p = ;p<n;p++)

        {

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

            {

                int j = i+p;

                Dp[i][j] = INF;

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

                {

                    if(k==j)

                        Dp[k][j] = ;

                    if(i==k)

                        Dp[i][k] = ;

                    if(Dp[i][j] >= Dp[i][k]+Dp[k+][j]+a[i]*b[j]*b[k])

                    {

                        vis[i][j] = k;

                        Dp[i][j] = Dp[i][k] + Dp[k+][j] + a[i]*b[j]*b[k];

                    }

                }

            }

        }

        printf("Case %d: ", k++);

        print(,n);

        printf("\n");

    }

    return ;

}

相关文章