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