| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
请教``` 关于 半径的遍历顺序 出现剪枝错误```为什么?#include <cstdlib>
#include <iostream>
#define inf 100000000
#define MAXN 22
using namespace std;
int N,ans,M,sem[MAXN],tem[MAXN];
inline int gets(int i){
return (i*(i+1)*i*(i+1))/4;
}
inline int geta(int i){
return (i*(i+1)*(2*i+1))/6;
}
void dfs(int num,int vum,int sum,int hlast,int rlast){
if(num==0&&vum==0){
ans=min(ans,sum);
return ;
}
int t=tem[num-1];
if(vum<tem[num-1] || sum+sem[num-1]>ans || 2*vum/(rlast)+sum>=ans) return ;
for(int i=num;i<=rlast;i++){ // 这里 我 的 i 从 rlast 到 num 就会出现 剪掉正确答案``是怎么回事? 别人这么剪不也没错啊
int th=(vum-t)/(i*i);
th=th<hlast?th:hlast;
for(int j=th;j>=num;j--){
if(t==0&&i*i*j!=vum)continue;
if (2 * (vum - i * i * j) / i + sum + 2 * i * j >= ans) continue;
if(num==M)sum=i*i;
dfs(num-1,vum-i*i*j,sum+2*i*j,j-1,i-1);
}
}
}
int main(int argc, char *argv[])
{
scanf("%d%d",&N,&M);
ans=inf;
fill(sem,sem+MAXN,inf);
tem[0]=0;
sem[0]=0;
for(int i=1;i<=20;i++){
tem[i]=tem[i-1]+i*i*i;
sem[i]=sem[i-1]+2*i*i;
}
dfs(M,N,0,N-1,N-1);
if(ans!=inf)printf("%d\n",ans);
else printf("0\n");
//system("PAUSE");
return EXIT_SUCCESS;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator