1 solutions

  • 0
    @ 2024-12-11 0:49:30

    C++ :

    #include<cstdio>
    #include<cstring>
    using namespace std;
    int a[201][201],b[201][201];
    int INF=1000000000;
    int max(int a,int b)
    {
    	if(a>b)
    	{
    		return a;
    	}
    	return b;
    }
    int Print(int i,int j)
    {
    	int n;
    	if(i>0)
    	{
    		n=i;
    		while(b[i][n]!=j)
    		{
    			n++;
    		}
    		Print(i-1,j-a[i][n]);
    		printf("%d ",n);
    	}
    }
    int main()
    {
        int F,V;
        while(~scanf("%d%d",&F,&V))
        {
            for(int i=1;i<=F;i++)
                for(int j=1;j<=V;j++)
                    scanf("%d",&a[i][j]);
            for(int i=1;i<=F;i++)
                for(int j=0;j<=V;j++)
                    b[i][j] = -INF;
            for(int i=1;i<=F;i++)
            {
                for(int j=i;j<=V;j++)
                {
                    if(b[i-1][j-1] + a[i][j] <= b[i][j-1])
                        b[i][j] = b[i][j-1];
                    else
                    {
                        b[i][j] = b[i-1][j-1] + a[i][j];
                    }
                }
            }
            printf("%d\n",b[F][V]);
            Print(F,b[F][V]);
            puts("");
        }
        return 0;
    }
    
    

    Pascal :

    var  
     a,b,c:array[1..100,1..100] of longint;  
     d:array[1..100] of longint;  
     i,j,k,max,f,v:longint;  
    begin  
     readln(f,v);  
     for i:=1 to f do  
      for j:=1 to v do  
       read(a[i,j]);  
     for i:=1 to v-f+1 do b[1,i]:=a[1,i];  
     for i:=2 to f do  
      for j:=i to v-f+i do  
       for k:=i-1 to j-1 do  
        if b[i-1,k]+a[i,j]>b[i,j] then  
        begin  
         b[i,j]:=b[i-1,k]+a[i,j];  
         c[i,j]:=k;  
        end;  
     max:=0;  
     for i:=f to v do  
      if b[f,i]>max then  
      begin  
       max:=b[f,i];  
       k:=i;  
      end;  
     writeln(max);  
     for i:=1 to f do  
     begin  
      d[i]:=k;  
      k:=c[f-i+1,k];  
     end;  
     for i:=f downto 1 do write(d[i],' ');  
    end.
    
    • 1

    Information

    ID
    755
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By