# GDOI2014 拯救莫莉斯

GDOI2014 拯救莫莉斯

Input

Output

Sample Input
33

654

123

789

Sample Output
36

Data Constraint

Code:

Const Maxs=1 << 8; Maxn=55; con=1061109567; Var f,g: array[0..maxn,0..maxs,0..maxs]of Longint; n,m,max: Longint; cost: array[0..maxn,0..maxs,0..2]of Longint; Procedure Init(); Var i,j,k,x: Longint; Begin Readln(n,m); max:=(1 << m)-1; For i:=1 To n DO Begin For j:=1 To m Do BEgin Read(x); For k:=0 To max Do if k And (1 << (j-1))>=(1 << (j-1)) Then BEgin Inc(cost[i][k][1],x); Inc(cost[i][k][2]); End; End; End; Fillchar(f,sizeof(f),63); Fillchar(g,sizeof(g),63); For k:=0 To max Do Begin f[1][k][0]:=cost[1][k][1]; g[1][k][0]:=cost[1][k][2]; End; End; Procedure Main(); Var i,j,k,n_l,a1,a2: Longint; Begin For i:=1 To n Do For j:=0 To max Do For k:=0 To max Do Begin if f[i][j][k]=con Then Continue; For n_l :=0 To max Do if (n_l or j or k or (j<<1) or (j>>1))and max=max Then if f[i][j][k]+cost[i+1][n_l][1]<f[i+1][n_l][j] Then BEgin

f[i+1][n_l][j]:=f[i][j][k]+cost[i+1][n_l][1]; g[i+1][n_l][j]:=g[i][j][k]+cost[i+1][n_l][2]; End; End; a2:=MaxLongint; For k:=0 To max Do if (f[n+1][0][k]<a2)or((f[n+1][0][k]=a2)and(g[n+1][0][k]<a1)) Then Begin a1:=g[n+1][0][k]; a2:=f[n+1][0][k]; End; Writeln(a1,' ',a2); End; Begin Init(); Main(); End. Jason Victor Yan