非常可乐 HDU - 1495
7 4 3 4 1 3 0 0 0Sample Output
NO
3
题意：很明确，要等分S。
Tip: 由于是全部倒完，所以如果S是奇数，必定不能平均分。在没判断是奇数的时候TLE，判断奇数后AC,证明了剪枝对搜索时间的重要性，毕竟搜索本身很暴力！！ 牢记复杂度判断，剪枝！！！！
#include <stdio.h> #include <string.h> int s,n,m; int que[100000]; int step[101][101][101]; int vis[101][101][101]; int flag; int judge(int a,int b, int c) //这里要注意要加上最后一个容器为0的情况 { if(a==b&&c==0) return 1; else if(a==c && b==0) return 1; else if(b==c && a==0) return 1; return 0; } void bfs() //对最初的S,0,0状态进行拓展，共12种情况 { memset(step,0,sizeof(step)); memset(vis,0,sizeof(vis)); int front=0,end=0; que[end++]=s; que[end++]=0; que[end++]=0; step[s][0][0]=0; vis[s][0][0]=1; while(front<end) { int a=que[front++]; int b=que[front++]; int c=que[front++]; if(a!=0) { if(a<=n-b) { int na=0; int nb=b+a; int nc=c; if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } else { int na=a-(n-b); int nb=n; int nc=c; if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } if(a<=m-c) { int na=0; int nb=b; int nc=c+a; if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } else { int na=a-(m-c); int nb=b; int nc=m; if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } } if(b!=0) { if(b>=s-a) { int na=s; int nb=b-(s-a); int nc=c; if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } else { int na=a+b; int nb=0; int nc=c; if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } if(b>m-c) { int na=a; int nb=b-(m-c); int nc=m; if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } else { int na=a; int nb=0; int nc=b+c; if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } } if(c!=0) { if(c>s-a) { int na=s; int nb=b; int nc=c-(s-a); if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } else { int na=a+c; int nb=b; int nc=0; if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } if(c>n-b) { int na=a; int nb=n; int nc=c-(n-b); if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } else { int na=a; int nb=b+c; int nc=0; if(step[na][nb][nc]==0) { step[na][nb][nc]=step[a][b][c]+1; vis[na][nb][nc]=1; que[end++]=na; que[end++]=nb; que[end++]=nc; if(judge(na,nb,nc)==1) { flag=1; printf("%d\n",step[na][nb][nc]); return ; } } } } } } int main(void) { while((scanf("%d%d%d",&s,&n,&m))==3) { if(s==0 && n==0 && m==0) return 0; if(s%2==1) // 如果是奇数，continue { printf("NO\n"); continue; } flag=-1; bfs(); if(flag==-1) printf("NO\n"); } }
投递CVTE等公司9个岗位 >