题解

50 条题解

  • 0
    @ 2016-06-05 22:05:46

    强搜剪枝,没有什么技巧,把想到的不可能情况能剪就剪,然后时间就没有问题了。
    ```c++
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int INF = 2147483647;

    int n,m,ans=INF;
    int r[50],h[50];

    void dfs(int hei,int last,int k)
    {
    if(hei==m+1&&last==0)
    {
    ans=min(k,ans);
    }
    else if(hei<=m)
    {
    if(k>=ans||last<=0) return;
    if(hei==1)
    {
    for(h[1]=m;h[1]<n;h[1]++)
    for(r[1]=m;r[1]<=(int)(sqrt(n/h[1]+0.5)+0.5);r[1]++) /* (int)(sqrt(n/h[1]+0.5)+0.5) */
    dfs(2,n-r[1]*r[1]*h[1],r[1]*h[1]*2+r[1]*r[1]);
    }
    else
    {
    if(last >= (r[hei-1]*r[hei-1]*h[hei-1])*(m-hei+1)) return;
    for(h[hei]=h[hei-1]-1;h[hei]>=(m-hei+1);h[hei]--)
    for(r[hei]=(m-hei+1);r[hei]*r[hei]*h[hei]<=last&&r[hei]<r[hei-1];r[hei]++)
    dfs(hei+1,last-r[hei]*r[hei]*h[hei],k+r[hei]*h[hei]*2);
    }
    }
    }

    int main()
    {
    scanf("%d%d",&n,&m);
    memset(r,0,sizeof(r));
    memset(h,0,sizeof(h));
    r[0]=INF;h[0]=INF;

    dfs(1,n,0);
    printf("%d\n",ans==INF ? 0:ans);
    return 0;
    }
    ```

  • 0
    @ 2015-10-13 19:57:08

    #include<cstdio>
    long S=0x7fffff;
    int n,m;
    void dfs(int v,int r,int h,int l,int s)
    {
    if(s>S)//最优化剪枝,若小于最优解,则直接返回
    return ;
    if(l==1)
    {
    for(int r0=l;r0<=r;r0++)
    if(v%(r0*r0)==0 && v/(r0*r0)<=h )
    if(s+(v/r0)*2<S)
    S=s+(v/r0)*2;
    return ;
    }
    for(int h0=l;h0<=h;h0++)
    for(int r0=l;r0<=r && r0*r0*h0<v;r0++)//可行化剪枝,易证得当还剩下L层时高度与半径最小为l,且要求体积必须小于剩下体积
    if(l==m)
    dfs(v-r0*r0*h0,r0-1,h0-1,l-1,s+r0*h0*2+r0*r0);
    else dfs(v-r0*r0*h0,r0-1,h0-1,l-1,s+r0*h0*2);
    return ;
    }
    int main()
    {
    scanf("%d %d",&n,&m);
    dfs(n,n/m,n/m,m,0);
    if(S==0x7fffff)
    printf("0");
    else printf("%ld",S);
    return 0;
    }

  • 0
    @ 2014-10-25 16:21:16

    卡时间卡过去了
    program p1297;
    var n,m,sum,num,i,j:longint;
    //
    function make(p1:longint):longint;
    var sum,i:longint;
    begin
    sum:=0;
    for i:=1 to p1 do sum:=sum+i*i*i;
    exit(sum);
    end;
    //
    function min(p1,p2:longint):longint;
    begin
    if p1>p2 then exit(p2)
    else exit(p1);
    end;
    //
    procedure dfs(k,s,h,v:longint);
    var i,j:longint;
    begin
    if v<make(m-k+1) then exit;
    if k=m+1 then
    begin
    if v<>0 then exit;
    num:=num+s*h*2;
    if num<sum then sum:=num;
    num:=num-s*h*2;
    exit;
    end;
    num:=num+s*h*2;
    if num>sum then
    begin
    num:=num-s*h*2;
    exit;
    end;
    for i:=m-k+1 to s-1 do
    for j:=m-k+1 to min(h-1,v div (i*i)) do
    dfs(k+1,i,j,v-i*i*j);
    num:=num-s*h*2;
    end;
    //
    begin
    read(n);
    read(m);sum:=1000000;
    for i:=m to n do
    for j:=m to n div (i*i) do
    begin
    num:=i*i;
    dfs(2,i,j,n-i*j*i);
    end;
    if sum=1000000 then sum:=0;
    write(sum);
    end.

  • 0
    @ 2014-10-18 11:58:29

    无解的太坑了....一直没想起会无解....额,我不会告诉你测试数据无解那个是1000 7的...开玩笑,我怎么可能告诉你输出是0呢...

  • 0
    @ 2014-04-03 18:18:00

    #include <iostream>

    using namespace std;

    int N, M;
    int minS = 9999999;

    void DFS(int n, int v, int s, int r, int h)
    {
    int i, j;

    if (n == 0) {
    if (s < minS && v == N) minS = s;
    }

    // 最优性剪枝
    if (s > minS) return;
    // 可行性剪枝
    if (v > N) return;
    // 最优性剪枝,判断当前状态下能构成的最小面积是否大于minS(强力剪枝:if s+2*(n-v)/r>=mins then exit;)
    if ((s + 2 * (N - v) / r) >= minS) return;
    // 可行性剪枝
    if ((r - 1) < n || (h - 1) < n) return;

    int nv, ns;
    for (i = r - 1; i > 0; --i) {
    for (j = h - 1; j > 0; --j) {
    nv = v + i * i * j;
    ns = s + 2 * i * j;
    if (n == M) ns += i * i;
    DFS(n - 1, nv, ns, i, j);
    }
    }
    }

    int main()
    {
    cin >> N >> M;
    DFS(M, 0, 0, 100, 100);
    if (minS == 9999999) minS = 0;
    cout << minS;
    return 0;
    }

  • 0
    @ 2013-04-24 12:45:58

    program cake;
    var
    i,r,h,vn,rn,hn,sn,best,m,n:integer;
    mins,minv:array[0..100] of integer;
    {=======prunning=======}
    procedure prunning;
    var
    k:integer;
    begin
    for k:=1 to n-1 do
    begin
    minv[k]:=minv[k-1]+k*k*k;
    mins[k]:=mins[k-1]+2*k*k;
    end;
    end;
    {=========dfs========}
    procedure dfs(i,rn,hn,vn,sn:integer);
    var
    r,h:integer;
    begin
    if i>n then
    begin
    if (sn<best) and (vn=0) then
    best:=sn;
    exit;
    end;
    if (sn+(2*vn) div rn < best) and (sn+mins[n-i+1] < best) and (vn >= minv[n-i+1]) and (vn>=0) then
    begin
    for r:=rn-1 downto n-i+1 do
    for h:=hn-1 downto n-i+1 do
    dfs(i+1,r,h,vn-r*r*h,sn+2*r*h);
    end;
    end;
    {================main===============}
    begin
    best:=maxint;
    fillchar(mins,sizeof(mins),0);
    fillchar(minv,sizeof(minv),0);
    readln(m);
    readln(n);
    prunning;
    for r:=trunc(sqrt((m-minv[n-1]) div n)) downto n do
    for h:=(m-minv[n-1]) div (r*r) downto n do
    begin
    dfs(2,r,h,m-r*r*h,2*r*h+r*r);
    end;
    if best<maxint then
    writeln(best)
    else
    writeln(0);
    end.

  • 0
    @ 2013-03-16 17:09:22

    program cake;
    var
    n,m,sum:longint;
    i,j:longint;
    procedure go(o,r,h,v,s:longint);
    var
    k,l:longint;
    begin
    if o=0
    then
    begin
    if (v=0)and(s<sum)
    then
    sum:=s;
    exit;
    end;
    k:=0;
    for l:=1 to o do
    k:=k+l*l*l;
    if v<k //可行性剪枝,判断剩下的体积是否足够做蛋糕
    then
    exit;
    k:=0;
    for l:=1 to o do
    k:=k+(r-l)*(r-l)*(r-l); //可行性剪枝,判断剩下的体积是否做得完
    if v>k
    then
    exit;
    if s>sum //最优化剪枝,判断面积是否符合条件
    then
    exit;
    if s+2*v/r>sum //最优化剪枝,剩下的s>=2*h*r=2*v/r
    then
    exit;
    for k:=r-1 downto o do
    for l:=h-1 downto o do
    go(o-1,k,l,v-k*k*l,s+2*k*l)
    end;

    begin
    readln(n);
    readln(m);
    sum:=maxlongint;
    for i:=m to trunc(sqrt(n)) do
    for j:=m to trunc(n/i/i) do
    go(m-1,i,j,n-i*i*j,i*i+2*i*j);
    if sum=maxlongint
    then
    sum:=0;
    writeln(sum);
    end.
    为什么最后一个点错了?求大牛指导

  • 0
    @ 2009-10-29 20:01:24

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    一点特殊剪枝没有,秒杀.........

    program noi;

    var

    n,m,r,h,i:longint;

    ans:longint;

    minv:array[0..20]of longint;

    function min(a,b:longint):longint;

    begin

    if ab then max:=a else max:=b;

    end;

    function maxv(r,h,k:longint):longint;

    var i:longint;

    begin

    maxv:=0;

    for i:=1 to k do

    begin

    dec(r);dec(h);

    if (r=v)and(minv[k-1]

  • 0
    @ 2009-10-29 13:08:34

    Accepted 有效得分:100 有效耗时:0ms

    伟大的数学推理剪枝~~~

  • 0
    @ 2009-10-05 18:19:51

    program xiti;

    type longint=integer;

    var i,j,n,m,ans:longint;

    t:array[1..20]of longint;

    procedure find(cs,r,h,s,v:longint);

    var ii,jj,qqq,ppp:longint;

    begin

    if s>=ans then exit;

    if (cs=m)and(v=0) then

    ans:=s;

    if (cs=m)or(v=0) then

    exit;

    if v

  • 0
    @ 2009-10-04 20:28:08

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    以前~

    一直没什么思路

    写了个裸搜

    没过

    今天

    灵感突发~

    加两个剪枝~

    居然过了~

    囧~

  • 0
    @ 2009-09-28 08:28:19

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案错误...程序输出比正确答案长

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 88ms

    ├ 测试数据 09:答案正确... 56ms

    ├ 测试数据 10:答案正确... 88ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:90 有效耗时:232ms

    囧~~~~~

    原来是0........囧~~~~~

  • 0
    @ 2009-07-20 16:26:02

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-var s,v,h,i,j,k,l,o,p,m,n,q,w,smin:longint;

    s1,v1,r1,h1:longint;

    minv:longint;

    procedure sea(i,ri,hi,si,vi:longint);

    var j,k,l,Rijia1,Hijia1,Sijia1,Vijia1:longint;

    begin

    minv:=0;

    if (i=m) then if (smin>si) and( vi=0) then begin smin:=si;exit;end;

    for k:=1 to m-i-1 do

    minv:=minv+sqr(k)*k;

    if si+2*vi/ri>smin then exit;

    if vi

  • 0
    @ 2009-07-20 15:29:35

    ├ 测试数据 01:答案正确... 0ms├ 测试数据 02:答案正确... 0ms├ 测试数据 03:答案正确... 0ms├ 测试数据 04:答案正确... 0ms├ 测试数据 05:答案正确... 0ms├ 测试数据 06:答案正确... 0ms├ 测试数据 07:答案正确... 0ms├ 测试数据 08:答案正确... 0ms├ 测试数据 09:答案正确... 0ms├ 测试数据 10:答案正确... 0ms-------------------------program cgb; var n,m,r,h,i:longint; opt:longint; minv:array[0..20]of longint; function min(a,b:longint):longint; begin if ab then max:=a else max:=b; end; function maxv(r,h,k:longint):longint; var i:longint; begin maxv:=0; for i:=1 to k do begin dec(r);dec(h); if (r=v)and(minv[k-1]

  • 0
    @ 2009-06-03 16:34:17

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 244ms

    ├ 测试数据 08:答案正确... 25ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:269ms

    剪枝太多了反而使程序更复杂,不能秒杀了......

  • 0
    @ 2009-05-09 15:04:36

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    只有两个常规的剪纸

    if(ss*(N-d+1)+s>re) break;

    if(vv*(N-d+1)+v>V) break;

    数据弱~连我这么弱的人也全0ms

  • 0
    @ 2009-04-04 21:56:15

    加一个最优化剪枝就AC了,秒杀!

    判断 2*r*(n-v)/r/r+s>=best 就可以了!

  • 0
    @ 2009-02-15 18:07:48

    搜索剪枝

    VJ上NOI中最好做的一题

  • 0
    @ 2009-02-14 17:04:08

    交了好多遍,数据蛮强的(可能我太弱了)

    1.最优解剪枝

    2.可行解剪枝(上限,下限)

    3.细节

    最优解别弄太大3000最够了

信息

ID
1297
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
1438
已通过
383
通过率
27%
被复制
2
上传者