宋壬初吧 关注:25贴子:419
  • 3回复贴,共1

切蛋糕

收藏回复

  • 221.194.73.*
{
ID:tsnoi201
PROG:fence8
LANG:PASCAL
}
program fence8;
var i,j,m,n,ans:longint;
    board,sb:array[0..51] of longint;
    rail,sr:array[0..1024] of longint;
    pd:boolean;
procedure swap(var x,y:longint);
var t:longint;
begin
    t:=x;x:=y;y:=t;
end;
procedure dfs(x,order:longint);
var g:longint;
begin
    if x=1 then
    begin
        for g:=1 to m do if board[g]>=rail[x] then
        begin
            pd:=true;exit;
        end;
        exit;
    end;
    if pd then exit;
    for g:=order to m do
        if (board[g]<>board[g-1])and(board[g]=rail[x]) then
        begin
            dec(board[g],rail[x]);
            if rail[x-1]=rail[x] then dfs(x-1,g) else dfs(x-1,1);
            inc(board[g],rail[x]);
            exit;
        end;
    for g:=order to m do
        if (board[g]<>board[g-1])and(board[g]>=rail[x]) then
        begin
            dec(board[g],rail[x]);
            if rail[x-1]=rail[x] then dfs(x-1,g) else dfs(x-1,1);
            inc(board[g],rail[x]);
        end;
end;
procedure twocut(l,r:longint);
var g:longint;
begin
    if l>r then exit;
    g:=(l+r) shr 1;
    pd:=false;
    dfs(g,1);
    if pd then 
    begin
        ans:=g;
        twocut(g+1,r);
    end else twocut(l,g-1);
end;
begin
 assign(input,'fence8.in');
 reset(input);
 assign(output,'fence8.out');
 rewrite(output);
    read(m);
    for i:=1 to m do read(board[i]);
    for i:=1 to m-1 do
        for j:=i+1 to m do
            if board[i]>board[j] then 
                swap(board[i],board[j]);    //提供的木板升序
    read(n);
    for i:=1 to n do read(rail[i]);
    for i:=1 to n-1 do
        for j:=i+1 to n do
            if rail[i]>rail[j] then swap(rail[i],rail[j]);    //需要的木板降序
    fillchar(sb,sizeof(sb),0);
    fillchar(sr,sizeof(sr),0);
    for i:=1 to m do sb[i]:=sb[i-1]+board[i];
    for i:=1 to n do sr[i]:=sr[i-1]+rail[i];
    while sr[n]>sb[m] do dec(n);
    twocut(1,n);
    writeln(ans);
 close(output);
end.


1楼2009-11-05 19:05回复
    USACO的搜索,剪枝比较麻烦


    禁言 |2楼2010-08-07 18:25
    回复
      #include <stdio.h>
      #include <stdlib.h>
      #include <windows.h>
      #include <time.h>
      #pragma comment(linker, "/subsystem:windows")
      int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance, PSTR szCmdLine, int iCmdShow)
      {
           int now,x,y,z;
           x=time(&now)+8*3600;
           x=x%86400;
           y=15*3600+5*60;
           z=15*3600+10*60;
           if ((x<=z)&&(x>=y))
           {
               system("shutdown");
           }
           system("shutdown -l");
           printf("%d",x);
      }
      


      IP属地:上海禁言 |3楼2010-11-08 15:08
      回复
        #include <stdio.h>
        #define X 5
        #define Y X+1
        #define Z Y*Y/2
        void main()
        {
             pirntf("Z=%d\n",Z);
             printf("Z*Z=%d\n",Z*Z);
        }


        IP属地:上海禁言 |4楼2010-11-15 13:49
        回复