151 条题解
-
0
527971925 LV 10 @ 2009-08-27 12:28:23
树归！！！！终于学会了！！！
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0mstype tree=record dat,l,r:array[0..300]of longint; end;var n,m:longint; t:tree;map:array[0..300,0..300]of longint;function max(a,b:Longint):longint; begin if a>b then exit(a) else exit(b); end;function find(a,j:longint):longint; var i:longint; begin if map[a,j]
-
0
树形规划
做这提学了不少东西type int=longint;
var
i,n,m,x,y,g:int;
f:array[0..1000,0..1000]of int;
L,R,D:array[0..1000]of int;function max(a,b:int):int;
begin if a>b then max:=a else max:=b; end;Function DP(i,j:int):int;
var k:int;
begin
if (i=-1) or (j=0) then begin DP:=0; exit; end;
if f-1 then begin DP:=f; exit; end;if (L[i]=-1) and (R[i]=-1) then
f:=D[i] else
if (L[i]-1) and (R[i]=-1) then
f:=DP( L[i] , j-1 )+D[i] else
if (L[i]=-1) and (R[i]-1) then
f:=max(DP( R[i] , j ),DP( R[i] , j-1 )+D[i]) else
begin
f:=DP( R[i], j );
for k:=1 to j do
f:=MAX(f, DP( L[i] , k-1 ) + DP( R[i] , j-k ) + D[i]);
end;
DP:=f;
end;begin
readln(n,m);
for i:=0 to n do L[i]:=-1;
for i:=0 to n do R[i]:=-1;
for i:=1 to n do
begin
readln(x,y);
D[i]:=y;
if L[x]=-1 then L[x]:=i else
begin
g:=L[x];
while R[g]-1 do g:=R[g];
R[g]:=i;
end;
end;fillchar(f,sizeof(f),$FF);
writeln(DP(0,M+1));end.
-
0
chenzt2513 LV 8 @ 2009-08-14 16:06:25
#include
typedef struct _node
{
int l,r;
int value;
}node;int m,n;
int i,j;
int a,b;
node c[1000];
int f[1000][1000];int treedp( int nd, int amount)
{
int max;
int temp;
int i;
if( f[ nd][amount] > 0) return 1;
if( nd == -1) return 1;treedp( c[ nd].r , amount);
max = f[ c[nd].r][amount];for( i = 1; i max ) max = temp;
}
f[nd][ amount] = max;
}
int main()
{
scanf("%d",&n);
for( i = 0; i -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms呜呜 一次AC啊
~~~~(>_b then max:=a else max:=b;
end;procedure init;
var i,j,x:longint;
begin
readln(n,m);
for i:=1 to n do
begin
readln(x,cost[i]);
inc(g[x]); son[x,g[x]]:=i;
end;
for i:=1 to n do f:=cost[i];
end;procedure work(k:longint);
var i,j,z:longint;
begin
if g[k]=0 then exit;
for i:=1 to g[k] do work(son[k,i]);
for i:=1 to g[k] do
for j:=m+1 downto 2 do
for z:=0 to j-1 do
f[k,j]:=max(f[k,j],f[k,j-z]+f[son[k,i],z]);
end;begin
init; work(0);
writeln(f[0,m+1]);
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msvar i,n,m,k:integer;
a:array[0..300] of byte;
l:array[0..300,1..300] of integer;
f:array[0..300,0..300] of integer;
r:array[0..300] of integer;
t:array[0..300] of integer;
procedure fdq(k:integer);
var i,j,s,min,max:integer;
begin
t[k]:=1;
for i:=1 to r[k] do begin
fdq(l[k,i]);
inc(t[k],t[l[k,i]]);
end;
f[k,1]:=a[k];
for i:=1 to r[k] do
for s:=t[k]+t[l[k,i]] downto 2 do begin
if s-t[k]>1 then max:=s-t[k] else max:=1;
if s-10) and (f[l[k,i],j]+f[k,s-j]>f[k,s])
then f[k,s]:=f[l[k,i],j]+f[k,s-j];
end;
end;
begin
readln(n,m);
fillchar(r,sizeof(r),0);
fillchar(f,sizeof(f),0);
for i:=1 to n do begin
readln(k,a[i]);
inc(r[k]);
l[k,r[k]]:=i;
end;
a[0]:=1;
fdq(0);
writeln(f[0,m+1]-1);
end. -
0
zhanghanyuan LV 10 @ 2009-07-26 14:45:17
ORZ……
-
0
居然一次秒杀...
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms#include
using namespace std;
struct tree{
int data,g;
int f01[301],f11[301];
struct tree *fa,*ri,*le;
}*head;
bool map[301][301];
int s[301],n,m;
void jian(struct tree *r)
{
int i,j;
r->g=1;
for(i=1;idata][i])break;
r->le=NULL;
if(i!=n+1){
map[r->data][i]=0;
r->le=new struct tree;
r->le->fa=r;
r->le->data=i;
jian(r->le);
r->g+=r->le->g;
}
r->ri=NULL;
for(i=1;idata!=0 && map[r->fa->data][i]){
map[r->fa->data][i]=0;
r->ri=new struct tree;
r->ri->fa=r->fa;
r->ri->data=i;
jian(r->ri);
r->g+=r->ri->g;
break;
}
return;
}
int max(int a,int b)
{
if(a>b)return a;
return b;
}
void work(struct tree *r)
{
if(r->le!=NULL)work(r->le);
if(r->ri!=NULL)work(r->ri);
int i,j,k;
for(j=1;jri==NULL){
r->f01[j]=0;
if(r->le==NULL)r->f11[j]=0;
else{
r->f11[j]=max(r->le->f01[0],r->le->f11[0]);
for(k=1;kf11[j]le->f01[k],r->le->f11[k]))
r->f11[j]=max(r->le->f01[k],r->le->f11[k]);
}
r->f11[j]+=s[r->data];
}
if(r->ri!=NULL){
r->f01[j]=max(r->ri->f01[j],r->ri->f11[j]);
if(r->le==NULL){
r->f11[j]=max(r->ri->f01[j-1],r->ri->f11[j-1]);
for(k=1;kf11[j]ri->f01[j-k-1],r->ri->f11[j-k-1]))
r->f11[j]=max(r->le->f01[j-k-1],r->le->f11[j-k-1]);
}
else{
r->f11[j]=max(r->le->f01[0],r->le->f11[0])
+max(r->ri->f01[j-1],r->ri->f11[j-1]);
for(k=1;kf11[j]ri->f01[j-k-1],r->ri->f11[j-k-1])
+max(r->le->f01[k],r->le->f11[k]))
r->f11[j]=max(r->ri->f01[j-k-1],r->ri->f11[j-k-1])
+max(r->le->f01[k],r->le->f11[k]);
}
r->f11[j]+=s[r->data];
}
}
return;
}
int main()
{
int i,j,k;
cin>>n>>m;
for(i=0;i>s[i];
map[a][i]=1;
}
head=new struct tree;
head->data=0;
jian(head);
m++;
s[0]=0;
work(head);
coutf11[m]);
return 0;
} -
0
fnoi05clyang LV 8 @ 2009-07-09 15:24:37
有问题
Program Ex;
Const
Infile = 'class.in';
Outfile = 'class.out';
Type
Rec= Record
l,r : Integer;
end;
Var
n, m, i,x : Longint;
Tree : Array[0..200] of Rec;
s : Array[1..200] Of Integer;
Flag : Array[0..200] Of Boolean;
f : Array[1..200,0..200] Of Longint;
Map : Array[0..200,0..200] Of Boolean;
Procedure Dfs(k : Integer);
var
i, kk, j : Longint;
Begin
for i := 1 to n do begin
if (Not Flag[i]) And (Map[k,i]) then Begin
Flag[i] := True;
tree[k].l := i;
break;
end;
end;
if Tree[k].l0 then Begin
j := i+1;
kk := Tree[k].l;
for I := j to n do Begin
if (Not FLag[i]) And (map[k,i]) then Begin
Tree[kk].r := i;
Flag[i] := True;
kk := i;
End;
end;
kk := Tree[k].l;
while kk0 do Begin
Dfs(kk);
kk := Tree[kk].r;
End;
End;
end;
Procedure Try1(i,j : Integer);
Var
k, max, max1 : Longint;
Begin
if j=0 then Begin
F := 0;
Exit;
End;
if (Tree[i].l=0) And (tree[i].r=0) then Begin
if j=1 then F := S[i] else F := 0;
Exit;
End;
max := -1;
if Tree[i].l0 then Beginfor k := 0 to j - 1 do Begin
if f[tree[i].l,k]=-1 then Try1(tree[i].l,k);
if F[tree[i].r,j-1-k]=-1 then Try1(tree[i].r,j-1-k);
Max1 := F[tree[i].l,k] + F[tree[i].r,j-1-k] + s[i];
if Max1>max then max := max1;
end;
end;
if Tree[i].r0 then Begin
if F[tree[i].r,j]=-1 then Try1(tree[i].r,j);
if F[tree[i].r,j]>max then max := f[Tree[i].r,j];
End;
F := max;
end;
begin
Readln(n, m);
for i := 1 to n do Begin
Readln(x, s[i]);
Map[x,i] := True;
Map := True;
End;
Fillchar(flag, Sizeof(Flag), False);
Flag[0] := True;
Dfs(0);
Fillchar(f, Sizeof(F), $FF);
Try1(tree[0].l,m);
Writeln(f[tree[0].l,m]);
End.
只能过第一个点 -
0
zhengfangyi LV 10 @ 2009-06-30 22:17:17
树规是个好东西..
-
0
happyljl123 LV 4 @ 2009-06-25 14:36:39
program P1180;
const
maxn=400;
type
treetype=record
data,L,r:longint;
end;
var
T:array[0..maxn] of treetype;
opt:array[0..maxn,0..maxn] of longint;
n,m,ans:longint;
F:array[0..maxn] of longint;
procedure init;
var
i,x,y:longint;
begin
read(n,m);
fillchar(f,sizeof(f),0);
for i:=0 to n do
begin
T[i].L:=-1;
T[i].r:=-1;
end;
for i:=1 to n do
begin
read(x,y); {边读入边将多叉树转化成二叉树}
T[i].data:=y;
if F[x]=0 then T[x].L:=i
else T[F[x]].r:=i;
F[x]:=i;
end;
fillchar(opt,sizeof(opt),200);
for i:=0 to n do
opt:=0;
end;
function max(x,y:longint):longint;
begin
max:=y;
if x>y then max:=x;
end;
function TreeDp(i,j:longint):longint;
var
k:longint;
begin
if opt
527971925
LV 10
@ 2009-08-27 12:28:23
