复习

数字三角形模型

1、摘花生

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1e3+10;

int f[N][N];

int n,m;
int a[N][N];

int main()
{
    int T;

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d%d",&n,&m);

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

        memset(f,0,sizeof f);

        f[1][1]=a[1][1];

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            f[i][j]=max(max(f[i-1][j],f[i][j-1])+a[i][j],f[i][j]);

        printf("%d\n",f[n][m]);
    }

    return 0;
}

2、最低通行费

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=210;

int n;

int a[N][N];
int f[N][N];

int main()
{
    scanf("%d",&n);

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

    memset(f,0x3f,sizeof f);

    f[1][1]=a[1][1];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            f[i][j]=min(min(f[i-1][j],f[i][j-1])+a[i][j],f[i][j]);
        }

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

    return 0;
}

最长上升子序列模型

1、怪盗基德的滑翔翼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=1e3+10;

int n;
int a[N];

int f[N];

int main()
{
    int T;

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d",&n);

        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)f[i]=1;
        for(int i=1;i<=n;i++)
            for(int j=i;j>=1;j--)if(a[i]>a[j])f[i]=max(f[i],f[j]+1);

        int ans=0;

        for(int i=1;i<=n;i++)ans=max(f[i],ans);
        for(int i=1;i<=n;i++)f[i]=1;
        for(int i=n;i>=1;i--)
            for(int j=i;j<=n;j++)
            if(a[i]>a[j])f[i]=max(f[i],f[j]+1);

        for(int i=1;i<=n;i++)ans=max(f[i],ans);
        printf("%d\n",ans);

    }
}

2、登山

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1e4+10;

int n;
int a[N];

int f1[N],f2[N];

int main()
{
    scanf("%d",&n);

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

    for(int i=1;i<=n;i++)f1[i]=f2[i]=1;

    for(int i=1;i<=n;i++)
        for(int j=i;j>=1;j--)if(a[i]>a[j])f1[i]=max(f1[i],f1[j]+1);

    for(int i=n;i>=1;i--)
        for(int j=i;j<=n;j++)if(a[i]>a[j])f2[i]=max(f2[i],f2[j]+1);

    int ans=0;

    for(int i=1;i<=n;i++)ans=max(ans,f1[i]+f2[i]-1);

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

    return 0;
}