Daily Archives: 23 8 月, 2012

HYSBZ 1079(着色方案）

Posted on by

Dp 神奇的状态转移……

Program fd;
const
   mo=1000000007;
var
   n,i,j:longint;
   c,tot:array[1..15] of longint;
   f:array[0..15,0..15,0..15,0..15,0..15,0..15] of int64;
function dfs(a1,a2,a3,a4,a5,last:longint):int64;
var
   i,j:longint;
   ans,q:int64;
   a:array[1..5] of longint;
begin
   if f[a1,a2,a3,a4,a5,last]>0 then exit(f[a1,a2,a3,a4,a5,last]);
   a[1]:=a1;a[2]:=a2;a[3]:=a3;a[4]:=a4;a[5]:=a5;
   ans:=0;
   for i:=1 to 5 do
      if (a[i]>0) then
      begin
         if (last=i+1) and (a[i]=1) then continue;

  //     if (last=i+1) then dec(a[i]);
         dec(a[i]);
         if i>1 then inc(a[i-1]);


         q:=dfs(a[1],a[2],a[3],a[4],a[5],i);
         inc(a[i]);
         if i>1 then dec(a[i-1]);

         if last=i+1 then ans:=(ans+(a[i]-1)*q) mod mo
         else ans:=(ans+a[i]*q) mod mo;


  //     if (last=i+1) then inc(a[i]);
      end;
   f[a1,a2,a3,a4,a5,last]:=ans;
   exit(ans);
end;
begin
   read(n);
   fillchar(tot,sizeof(tot),0);
   for i:=1 to n do
   begin
      read(c[i]);
      inc(tot[c[i]]);
   end;
   fillchar(f,sizeof(f),0);
   for i:=1 to n do f[0,0,0,0,0,i]:=1;
   writeln(dfs(tot[1],tot[2],tot[3],tot[4],tot[5],0));



end.

POJ 1818(贪心）

Posted on by

让每个人每局都与可战胜的人中最强的打,看有无可行解……

Program p1818;
var
   n,x,k,i,j,mid:longint;
   q:array[1..5100] of longint;
   f:array[1..5100] of longint;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function is_ac(person:longint):boolean;
var
   i,j,l,h,t:longint;
   size:longint;
begin
   fillchar(f,sizeof(f),0);
   fillchar(q,sizeof(q),0);
   q[1]:=person;
   size:=1;
   f[person]:=1;
   h:=1;t:=1;
   for l:=2 to x+1 do
   begin
      for i:=h to t do
      begin
         for j:=max(1,q[i]-k) to n do
         begin
            if f[j]=0 then
            begin
               inc(size);
               q[size]:=j;
               f[j]:=l;
               break;
            end;
         end;
      end;

      t:=size;

   end;

   if (size<n) then exit(false)
   else exit(true);


end;
begin
   read(n,k);
   x:=0;
   i:=1;
   while (i<n) do
   begin
      inc(x);
      i:=i shl 1;
   end;

   i:=1;j:=n;
   if is_ac(j) then i:=j;
   while (j-i>1) do
   begin
      mid:=(i+j) shr 1;
      if is_ac(mid) then i:=mid else j:=mid;
   end;
   writeln(i);
end.