50 条题解
-
1BeNoble LV 8 @ 2016-11-17 21:30:03
-
02016-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;
}
``` -
02015-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;
} -
02014-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. -
02014-10-18 11:58:29@
无解的太坑了....一直没想起会无解....额,我不会告诉你测试数据无解那个是1000 7的...开玩笑,我怎么可能告诉你输出是0呢...
-
02014-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;
} -
02013-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. -
02013-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.
为什么最后一个点错了?求大牛指导 -
02009-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] -
02009-10-29 13:08:34@
Accepted 有效得分:100 有效耗时:0ms
伟大的数学推理剪枝~~~
-
02009-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 -
02009-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以前~
一直没什么思路
写了个裸搜
没过
今天
灵感突发~
加两个剪枝~
居然过了~囧~
-
02009-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........囧~~~~~ -
02009-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 -
02009-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]
-
02009-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剪枝太多了反而使程序更复杂,不能秒杀了......
-
02009-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 -
02009-04-04 21:56:15@
加一个最优化剪枝就AC了,秒杀!
判断 2*r*(n-v)/r/r+s>=best 就可以了! -
02009-02-15 18:07:48@
搜索剪枝
VJ上NOI中最好做的一题 -
02009-02-14 17:04:08@
交了好多遍,数据蛮强的(可能我太弱了)
1.最优解剪枝
2.可行解剪枝(上限,下限)
3.细节
最优解别弄太大3000最够了