1 solutions
-
0
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