1 条题解

  • 0
    @ 2021-6-14 23:29:10

    C++ :

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
     
    const int maxn1=40;
    const int maxn2=10000;
    int n,m,ans=0,f[maxn1][maxn2];
    int a[maxn1+20],b[maxn2+20];
     
    void dfs(int step,int s,int e)
    {
      int i,j,k;
      if(step>m)
        {
          if(ans<e-1)for(ans=e-1,i=1;i<=m;i++)b[i]=a[i];
          return;
    	}
      for(k=e;k>=s;k--)
        {
          j=a[step-1]*n;
          for(i=0;i<=j;i++)f[step][i]=f[step-1][i];
          memset(&f[step][j+1],25,sizeof(int)*((n*k+1-j)+10));
          
          for(j=n*k,i=k;i<=j;i++)
            f[step][i]=min(f[step][i],f[step][i-k]+1);
          for(i=e;i<=j+1;i++)if(f[step][i]>n)
            {
              a[step]=k,dfs(step+1,k+1,i);
              break;
    		}
    	}
    }
     
    int main()
    {
      int i;
      memset(f[1],25,sizeof(f[1]));
      scanf("%d%d",&n,&m);
      for(i=0;i<=n;i++)f[1][i]=i;
      a[1]=1,dfs(2,2,n+1);
      for(i=1;i<m;i++)printf("%d ",b[i]);
      printf("%d\nMAX=%d\n",b[m],ans);
      return 0;
    }
    
    

    Pascal :

    var ans,a,b:array[1..1000]of longint;
        m,n,max,i:integer;
    function  conti(p:integer):integer;
     var time:integer;
         i,k:integer;
     begin
      for i:=1 to 1000 do b[i]:=maxlongint;
      for i:=1 to p do  b[a[i]]:=1;
      time:=0;
      repeat
       inc(time);
       for k:=1 to p do
        if (time>a[k])and(b[time-a[k]]+1<b[time]) then b[time]:=b[time-a[k]]+1;
      until b[time]>m;
      conti:=time;
     end;
    procedure search(i:integer);
     var j,k:integer;
     begin
      if i>n then
       begin
        if conti(i-1)-1>max
         then begin max:=conti(i-1)-1;for i:=1 to 10 do ans[i]:=a[i]; end;
        exit;
       end
       else begin
             j:=conti(i-1);
             for k:=j downto a[i-1]+1 do begin a[i]:=k;search(i+1); end;
            end;
     end;
    procedure print;
     var i:integer;
     begin
     end;
    begin
     readln(m,n);
     a[1]:=1;
     search(2);
     for i:=1 to 10 do
      begin
       if (ans[i+1]=0)and(ans[i]<>0) then begin writeln(ans[i]);break; end;
       if ans[i]<>0 then write(ans[i],' ') else break;
      end;
     writeln('MAX=',max);
    end.
    
    • 1

    信息

    ID
    198
    时间
    1000ms
    内存
    125MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者