头像

跨过那座山


访客:952

离线:1个月前


活动打卡代码 AcWing 901. 滑雪

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
const int N=310;
int f[N][N];
int h[N][N];
 int n,m;
int dp(int x,int y)
{
    if(f[x][y]!=-1) return f[x][y];

    f[x][y]=1; //对于每一个坐标,最次的情况下,也可以为1

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

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


     }


    return f[x][y];


}
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      cin>>h[i][j];

      memset(f,-1,sizeof(f)); //将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\n",res);

    return 0;
}



#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<vector>

using namespace std;
const int N=6010;
vector<int > hh[N];
int f[N][2];
int happy[N];  //相当于每个节点的权值
bool sd[N];
void dfs(int u)
{
     f[u][1]=happy[u];

    for(int i=0;i<hh[u].size();i++)
     {
         int j=hh[u][i];
         dfs(j);
         f[u][1]=f[u][1]+f[j][0];  //包含父节点时,他的孩子节点都不能选
         f[u][0]=f[u][0]+max(f[j][0],f[j][1]);  //不包含父节点,从他的孩子节点里面选一个最大值

     }
    return;

}
int main()
{
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
     cin>>happy[i];

    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;   //b为父节点,a为孩子节点
        hh[b].push_back(a);
        sd[a]=true;

    }

    int root=1;
    while(sd[root]) root++;

    dfs(root);

    printf("%d\n",max(f[root][1],f[root][0]));



    return 0;
}


活动打卡代码 AcWing 1226. 包子凑数

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
const int N=10010;
bool f[110][N];
int v[N];
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    memset(f,0,sizeof(f));
    int n;
    cin>>n;
    int d=0;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        d=gcd(d,v[i]); 

    }
    if(d!=1) printf("INF\n");
    else
    {
        f[0][0]=true;  //注意初始化,注意初始化,注意初始化
        for(int i=1;i<=n;i++)  //物品的数量
          for(int j=0;j<=N;j++)  //注意“=”号,j表示体积
           {
               f[i][j]=f[i-1][j];
               if(j>=v[i])
               f[i][j]=f[i][j]|f[i][j-v[i]];

           }

        int res=0;
        for(int i=0;i<=N;i++)
         {
             if(!f[n][i])    //前n个物品,总体积为0,1,2,3,4,5----N,判断是否可以凑出来
              res++;

         }
        printf("%d\n",res);

    }


    return 0;
}


活动打卡代码 AcWing 1217. 垒骰子

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
const int N=6;
const int mod=1e9+7;
typedef long long ll;
int a[N][N];
int shang(int g)

{
    if(g>=3) return g-3;  //注意为等于,3,4,5
    else
    return g+3;    //0,1,2

}

void hh1(int c[],int a[],int b[][N])
{
    int temp[N]={0};
    for(int i=0;i<N;i++)
     for(int j=0;j<N;j++)
       temp[i]=(temp[i]+(ll)a[j]*b[j][i])%mod;
    memcpy(c,temp,sizeof(temp));

}
void hh2(int c[][N],int a[][N],int b[][N])
{
    int temp[N][N]={0};
    for(int i=0;i<N;i++) 
      for(int j=0;j<N;j++)
       for(int k=0;k<N;k++)
        temp[i][j]=(temp[i][j]+(ll)a[i][k]*b[k][j])%mod;
        memcpy(c,temp,sizeof(temp));


}

int main()
{
    int n,m;
    cin>>n>>m;

    int f1[N]={4,4,4,4,4,4};//数组赋值的时候,要直接赋值,不能先定义,在赋值
                             //表示的是有一个骰子的时候,最上面的数字为1,2,3,4,5,6的个数
    for(int i=0;i<N;i++)
     for(int j=0;j<N;j++)
       a[i][j]=4;

    while(m--)
    {
        int x,y;
        cin>>x>>y;
        x--,y--;  //注意将骰子的数量都减去1
        a[x][shang(y)]=0;
        a[y][shang(x)]=0;

    }

    int k=n-1;
    while(k)
    {
         if(k&1) hh1(f1,f1,a);   //res=res*a;
         hh2(a,a,a);             //a=a*a

         k=k>>1;


    }

    int res=0;
    for(int i=0;i<N;i++)
     res=(res+f1[i])%mod;//最上面的数字为1,2,3,4,5,6数量的总和
     printf("%d\n",res);
    return 0;
}



#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>

using namespace std;
typedef long long ll;
 int n,m;
const int N=3;
void hh1(int c[],int a[],int b[][N])
{
    int temp[N]={0};  //没有赋值的自动设置为0

    for(int i=0;i<N;i++)
     for(int j=0;j<N;j++)


           temp[i]=(temp[i]+(ll)a[j]*b[j][i])%m;

    memcpy(c,temp,sizeof(temp));

}
void hh2(int c[][N],int a[][N],int b[][N])
{
   int temp[N][N]={0};

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

              temp[i][j]=(temp[i][j]+(ll)a[i][k]*b[k][j])%m;

          }
    memcpy(c,temp,sizeof(temp));  



}
int main()
{

    cin>>n>>m;


    int f1[N]={1,1,1};
    int a[N][N]={
        {0,1,0},
        {1,1,1},
        {0,0,1}

    };

    int k=n-1;
    while(k)
    {

        if(k&1) hh1(f1,f1,a);   //res=res*a
        hh2(a,a,a);   //a=a*a
        k=k>>1; 

    }
    printf("%d ",f1[2]);


    return 0;
}


活动打卡代码 AcWing 1078. 旅游规划

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
const int N=2e5+10;
int d1[N],d2[N],p1[N],up[N];
vector<int > hh[N];
int maxd;
bool comp(int a,int b)
{
    return a<b;
}
void dfs_d(int u,int fath)
{

    for(int i=0;i<hh[u].size();i++)
    {
        int j=hh[u][i];
        if(j==fath) continue;

        dfs_d(j,u);

        int distance=d1[j]+1;
        if(distance>d1[u])
        {
            d2[u]=d1[u];
            d1[u]=distance;
            p1[u]=j;
        }
        else if(distance>d2[u])
        {
            d2[u]=distance;
        }


    }

    maxd=max(maxd,d2[u]+d1[u]);//枚举完u的每一个孩子节点以后,再求最大值    

    return;
}
void dfs_up(int u,int fath)
{

    for(int i=0;i<hh[u].size();i++)
    {
        int j=hh[u][i];
        if(j==fath) continue;

        up[j]=up[u]+1;   //父节点的最大距离+1(父节点到孩子节点的距离为1)
        if(p1[u]==j)

            up[j]=max(up[j],d2[u]+1);


        else
        up[j]=max(up[j],d1[u]+1);

        dfs_up(j,u);//不要忘记递归

    }
    return;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        hh[a].push_back(b);
        hh[b].push_back(a);
    }
    dfs_d(0,-1);
    dfs_up(0,-1);

    for(int i=0;i<n;i++)  //枚举每一个编号
    {
        int df[3];
        df[0]=up[i];df[1]=d1[i];df[2]=d2[i];

        sort(df,df+3,comp);  

        if(df[1]+df[2]==maxd)  //找最大的两个的值
        printf("%d\n",i);


    }

    return 0;

}


活动打卡代码 AcWing 1070. 括号配对

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
const int N=110;
char s[N];
int f[N][N];
int main()
{
    cin>>s;
    int n=strlen(s);

    for(int len=1;len<=n;len++)//注意要有等号
      for(int l=0;l+len-1<n;l++)
       {
           int r=l+len-1;

           if(s[l]=='['&&s[r]==']'||s[l]=='('&&s[r]==')')
           f[l][r]=max(f[l][r],f[l+1][r-1]+2);

           f[l][r]=max(f[l][r],f[l+1][r]);
           f[l][r]=max(f[l][r],f[l][r-1]);
           f[l][r]=max(f[l][r],f[l+1][r-1]);
           for(int k=l;k<r;k++)

               f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);

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



}


活动打卡代码 AcWing 1220. 生命之树

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
const int N=1e5+10;
typedef long long ll;
vector<int > hh[N];
ll f[N];
int w[N];
void dfs(int u,int fath)
{
 f[u]=w[u];

 for(int i=0;i<hh[u].size();i++)
{
    if(hh[u][i]==fath) continue;

    dfs(hh[u][i],u);
    f[u]=f[u]+max(0ll,f[hh[u][i]]);

}    

  return;  
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        hh[a].push_back(b);
        hh[b].push_back(a);


    }
    dfs(1,-1);
    ll res=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    res=max(res,f[i]);
    printf("%lld\n",res);


    return 0;
}


活动打卡代码 AcWing 1222. 密码脱落

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
const int N=1110;
char s[N];
int f[N][N];

int main()
{
    cin>>s;
    int n=strlen(s);

    for(int len=1;len<=n;len++)   //先枚举长度
      for(int l=0;len+l-1<n;l++)
       {
           int r=len+l-1;
           if(len==1) 
           f[l][r]=1;
           else
           {
               if(s[l]==s[r])     //都在时,要特判一下,只有两端的字母一样时,才算
               f[l][r]=max(f[l][r],f[l+1][r-1]+2);//l,r都在区间

               f[l][r]=max(f[l][r],f[l+1][r]);  //  l不在,r在
               f[l][r]=max(f[l][r],f[l][r-1]);  //l在,r不在
               f[l][r]=max(f[l][r],f[l+1][r-1]); //l,r都不在

           }


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


    return 0;
}


活动打卡代码 AcWing 1047. 糖果

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N=110;
int f[N][N];
int a[N];
int n,k;
int main()
{
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;    //一个都不选时,总和一定为0,f[0][1-]都是无意义的
                  //初始化为无穷
    cin>>n>>k;        
    for(int i=1;i<=n;i++)
    cin>>a[i];

    for(int i=1;i<=n;i++) //所以没有等于号
     for(int j=0;j<k;j++) //注意为小于,j表示余数为多少,余数不可能比除数大,
        {
            f[i][j]=max(f[i][j],f[i-1][j]);

            f[i][j]=max(f[i][j],f[i-1][((j-a[i]+k)%k+k)%k]+a[i]);

           }                 

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







    return 0;

}