头像

走不到也得走


访客:4937

离线:12天前


活动打卡代码 AcWing 902. 最短编辑距离

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1010;

char a[N],b[N];
int f[N][N];
int n,m;

int main()
{
    cin>>n>>a+1;
    cin>>m>>b+1;

    for(int i=1;i<=m;i++)f[0][i]=i;
    for(int i=1;i<=n;i++)f[i][0]=i;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {  
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    printf("%d\n",f[n][m]);
}



#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=310;

int n,m;
int f[N][N],h[N][N];

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int dp(int x,int y)
{
    int &v=f[x][y];
    if(v!=-1)return v;
    v=1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[x][y])
        v=max(dp(a,b)+1,v);
    }
    return v;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           scanf("%d",&h[i][j]);


    memset(f,-1,sizeof f);
    int res=0;
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
         res=max(res,dp(i,j));
    printf("%d",res);
    return 0;
}



#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=6060;
int f[N][2];
int h[N],e[N],ne[N],idx;
int happy[N];
bool  has_fa[N];
int n;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
    f[u][1]=happy[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][1]+=f[j][0];
        f[u][0]+=max(f[j][0],f[j][1]);
        //printf("%d %d\n",f[u][1],f[u][0]);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&happy[i]);

    }
    memset(h,-1,sizeof h);
    int a,b;
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&a,&b);
        add(b,a);//注意有向边的方向
        has_fa[a]=true;    
    }
    int root=1;
    while(has_fa[root])root++;    

    dfs(root);
    printf("%d",max(f[root][0],f[root][1]));
    return 0;
}



#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int q[N];
int a[N];
int main()
{
    int n;
    cin>>n;
    int len=0;
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    q[0]=-2e9;

    for(int i=0;i<n;i++)
    {
        int l=0,r=len;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(q[mid]<a[i])l=mid;
            else r=mid-1;
        }
        len=max(len,r+1);
        q[r+1]=a[i];
    }

    cout<<len<<endl;



    return 0;
}



#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;

int a[N],f[N][N];
int s[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){scanf("%d",&a[i]);
    s[i]=a[i];

    }
    for(int i=1;i<=n;i++)s[i]+=s[i-1];

    for(int len=1;len<=n-1;len++)//i从1开始,所以小于n-1
    {   
        for(int i=1;i+len<=n;i++)
        {    
           int l=i,r=i+len; 
           f[l][r]=1e9;
           for(int k=l;k<r;k++)
           f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }

    }
    printf("%d",f[1][n]);
    return 0;
}



#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;

int f[N][N];
char a[N],b[N];
int main()
{
    int n,m;
    cin>>n>>m;
    cin>>a+1>>b+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
         {
             f[i][j]=max(f[i][j-1],f[i-1][j]);
             if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
         }
    cout<<f[n][m]<<endl;
    return 0;
}




#include<iostream>
using namespace std;
const int N=1010;
int f[N],a[N],g[N];
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++)
    {
         f[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j])
            {
                if(f[i]<f[j]+1)
                {
                    f[i]=f[j]+1;
                    g[i]=j;
                }

            }

        }
    }
    int res=1;
    for(int i=1;i<=n;i++)
    res=max(res,f[i]);
    cout<<res<<endl;

    return 0;
}



#include<iostream>
using namespace std;
const int N=510,INF=1e9;
int f[N][N];
int a[N][N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
       for(int j=1;j<=i;j++)
           cin>>a[i][j];

    for(int i=0;i<=n;i++)    
       for(int j=0;j<=i+1;j++)
           f[i][j]=-INF;
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)       
        for(int j=1;j<=i;j++)
           f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
    int res=0;
    for(int i=0;i<=n;i++)res=max(res,f[n][i]);
    cout<<res<<endl;
    return 0;
}



#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=0;j<s[i];j++)
            cin>>v[i][j]>>w[i][j];

    }
    for(int i=1;i<=n;i++)
      for(int j=m;j>=0;j--)
         for(int k=0;k<s[i];k++)
            if(j>=v[i][k])f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);

    cout<<f[m]<<endl;
    return 0;
}



#include<iostream>
#include<algorithm>
using namespace std;
const int N=12010,M=2010;
int v[N],w[N];
int f[M];
int main()
{
    int n,m;
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        int k=1;
        while(k<=c)
        {   
            cnt++;
            v[cnt]=a*k;
            w[cnt]=b*k;
            c-=k;
            k*=2;
        }
        if(c>0)
        {   
            cnt++;
            v[cnt]=c*a;
            w[cnt]=c*b;
        }

    }
    n=cnt;
    for(int i=1;i<=n;i++)
       for(int j=m;j>=v[i];j--)
           f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m]<<endl;
    return 0;
}