澳门新葡亰信誉平台游戏HDU 1257 最少拦截系统

by admin on 2020年1月28日

求最长不降子序列问题

#include<stdio.h>
#include<string.h>
int main(void)
{
    int i;
    int n,x;
    int m=1;
    char s[200];
    FILE *in,*out;
    in=fopen(“game.in”,”r”);
    ut=fopen(“game.out”,”w”);
    fscanf(in,”%d%s”,&n,s);
    if((x=strlen(s))!=n)
      fprintf(out,”error!n”);
    else
    {
      for(i=0;i<x;i++)
      {
        if(s[i]==’r’) m++;
      }
      fprintf(out,”%dn”,m);
    }
    fclose(in);
    fclose(out);
    return 0;
}

没事敲了个最长公共子序列,按照自己笔记本上模板算法!
先敲了一个递归算法的,敲时就感觉费事儿!一提交,果断超时!无语,……….

#include<stdio.h>
#include<string.h>
int c[1001][1001];
int main()
{
 char a[1001],b[1001];
 int i,j,la,lb;
 while(scanf(“%s %s”,a,b)!=EOF)
 {
  la=strlen(a);
  lb=strlen(b);
  for(i=0;i<la;i++)c[i][0]=0;
  for(i=0;i<lb;i++)c[0][i]=0;
  for(i=1;i<=la;i++)
   for(j=1;j<=lb;j++)
    if(a[i-1]==b[j-1])
     c[i][j]=c[i-1][j-1]+1;
    else if(c[i-1][j]>=c[i][j-1])
     c[i][j]=c[i-1][j];
    else c[i][j]=c[i][j-1];
  printf(“%dn”,c[la][lb]);
 }
 return 0;
}

另外3个题均AC全部点

int main()
{
 int m,n,k;
 while(scanf(“%s%s”,a,b)!=EOF)
 {
  m=strlen(a);
     n=strlen(b);
     printf(“%dn”,lcs_len(m,n));
 }
 return 0;
}

#include<stdio.h>
int main(void)
{
    int i,j,k;
    int n;
    int x[30][30];
    int t,c;
    FILE *in,*out;
    in=fopen(“sos.in”,”r”);
    ut=fopen(“sos.out”,”w”);
    fscanf(in,”%d”,&n);
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
      {
        fscanf(in,”%d”,&x[i][j]);
        if(x[i][j]==1) x[i][j]=-1; else x[i][j]=1000;
      }
    x[0][0]=1;
    c=n-1;
    while(x[c][c]==1000)
    {
      for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
          if(i>0)
            if(x[i-1][j]!=-1)
              if((t=x[i-1][j]+1)<x[i][j])
                x[i][j]=t;
          if(i<c)
            if(x[i+1][j]!=-1)
              if((t=x[i+1][j]+1)<x[i][j])
                x[i][j]=t;
          if(j>0)
            if(x[i][j-1]!=-1)
              if((t=x[i][j-1]+1)<x[i][j])
                x[i][j]=t;
          if(j<c)
            if(x[i][j+1]!=-1)
              if((t=x[i][j+1]+1)<x[i][j])
                x[i][j]=t;
        }
    }
    fprintf(out,”%dn”,x[c][c]);
    fclose(in);
    fclose(out);
    return 0;
}
               
其中love.c过3个点,其余7个点超时或崩溃

AC:

love.c

还好哥有个非递归模板,敲完一交。31ms!   差距好大啊,以后就用非递归吧!

题目难度还可以,排名第三,成绩330,但是与第一和第二还有一定差距,努力啊

int lcs_len(int m,int n)
{
 int i,j;
 for(i=0;i<=m;i++)
 c[i][0]=0;
 for(i=0;i<=n;i++)
 c[0][i]=0;
 for(i=1;i<=m;i++)
 {
  for(j=1;j<=n;j++)
  {
   if(a[i-1]==b[j-1])
   c[i][j]=c[i-1][j-1]+1;
   else if(c[i-1][j]>=c[i][j-1])
   c[i][j]=c[i-1][j];
   else
   c[i][j]=c[i][j-1];
  }
 }
 return c[m][n];
}

我的代码:

模板在此

score.c

#include<stdio.h>
#include<string.h>
char a[10001],b[10001];
int c[10001][10001];

#include<stdio.h>
#include<stdio.h>
char s[40];
int jian(char a[40],char b[40])
{
    int i,x;
    int lena,lenb;
    memset(s,0,sizeof(s));
    lena=strlen(a);
    lenb=strlen(b);
    for(i=0;i<40;i++)
    {
      if(a[i])
        a[i]-=’0′;
      if(b[i])
        b[i]-=’0′;
    }
    x=39-lena;
    lena–;
    for(i=39;i>x;i–,lena–) a[i]=a[lena];
    for(i=0;i<=x;i++) a[i]=0;
    x=39-lenb;
    lenb–;
    for(i=39;i>x;i–,lenb–) b[i]=b[lenb];
    for(i=0;i<=x;i++) b[i]=0;
    i=0;
    while(a[i]==0) i++;
    for(;i<39;i++) { a[i]–; a[i+1]+=10; }
    for(i=0;i<40;i++)
      s[i]=a[i]-b[i];
    for(i=39;i>0;i–)
    {
      s[i-1]+=s[i]/10;
      s[i]%=10;
    }
}
int main(void)
{
    int i,k;
    int n;
    char max[3][40]={0};
    char my[3][40]={0};
    char temp[40]={0};
    int r,t;
    FILE *in,*out;
    in=fopen(“score.in”,”r”);
    ut=fopen(“score.out”,”w”);
    fscanf(in,”%s%s%s”,max[0],max[1],max[2]);
    strcpy(my[0],max[0]);
    strcpy(my[1],max[1]);
    strcpy(my[2],max[2]);
    fscanf(in,”%d”,&n);
    for(i=0;i<n;i++)
    {
      fscanf(in,”%s”,temp);
      r=strcmp(temp,max[0]);
      t=strlen(temp)-strlen(max[0]);
      if((t>0)||((r>0)&&(t==0))) { strcpy(max[0],temp);  }
      fscanf(in,”%s”,temp);
      r=strcmp(temp,max[1]);
      t=strlen(temp)-strlen(max[1]);
      if((t>0)||((r>0)&&(t==0))) { strcpy(max[1],temp);  }
      fscanf(in,”%s”,temp);
      r=strcmp(temp,max[2]);
      t=strlen(temp)-strlen(max[2]);
      if((t>0)||((r>0)&&(t==0))) { strcpy(max[2],temp);  }
    }
    for(k=0;k<3;k++)
    {
      if(!strcmp(max[k],my[k])) fprintf(out,”0 “);
      else
      {
          jian(max[k],my[k]);
          i=0;
          while(s[i]==0) i++;
          for(;i<40;i++) fprintf(out,”%d”,s[i]);
          fprintf(out,” “);
      }
    }
    fprintf(out,”n”);
    fclose(in);
    fclose(out);
    return 0;
}
   
       
sos.c

game.c

#include<stdio.h>
typedef struct
{
        int x; /*数字*/
        int n;
}DATA;
/*
void qsort(int low,int high,DATA key[])
{
     int i=low,j=high;
     DATA tag;
     if(i<j)
     {
       tag=key[low];
       do
       {
         while(tag.x<key[j].x && i<j) j–;
         if(i<j)
         {
           key[i]=key[j];
           i++;
           while(tag.x>=key[i].x && i<j) i++;
           if(i<j)
           {
             key[j]=key[i];
             j–;
           }
         }
       }
       while(i<j);
       key[i]=tag;
       qsort(low,i-1;key);
       qsort(j+1,high,key);
     }
}
*/
int main(void)
{
    int i,j,k;
    DATA line[27001]={0};
    int n;
    int max=0;
    FILE *in,*out;
    in=fopen(“love.in”,”r”);
    ut=fopen(“love.out”,”w”);
    fscanf(in,”%d”,&n);
    for(i=0;i<n;i++) fscanf(in,”%d”,&line[i].x);
    for(i=n-1;i>=0;i–)
    {
      line[i].n=1;
      for(j=i+1;j<n;j++)
      {
        if(line[i].x<=line[j].x)
          if(line[j].n+1>line[i].n)
            line[i].n=line[j].n+1;
      }
      if(line[i].n>max) max=line[i].n;
    }
    fprintf(out,”%d”,max);
    fclose(in);
    fclose(out);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图