题意:给你三个桶,容量分别为A,B,C,然后问你用这三个没有刻度的桶可以量出多少不同容量的水。0<=A,B,C<=255
一开始认为如果开三维的256^3会跪,但是想不到什么别的好一点的方法,就直接开三维了,结果就过了。这样说来,此题很水。不知道有没有更好的方法。
1 #include <stdio.h> 2 #include <string.h> 3 const int maxn = 1<<8; 4 bool d[maxn][maxn][maxn]; 5 bool vis[maxn*3]; 6 int A,B,C; 7 8 void dp(int n,int m,int k){ 9 if(d[n][m][k]) return; 10 d[n][m][k] = 1; 11 vis[n] = 1; 12 vis[m] = 1; 13 vis[k] = 1; 14 vis[n+m] = 1; 15 vis[n+k] = 1; 16 vis[m+k] = 1; 17 vis[n+m+k] = 1; 18 19 dp(A,m,k); 20 if(n+m <= B) dp(0,n+m,k); 21 else dp(n+m-B,B,k); 22 if(n+k <= C) dp(0,m,k+n); 23 else dp(n+k-C,m,C); 24 25 dp(n,B,k); 26 if(n+m <= A) dp(n+m,0,k); 27 else dp(A,n+m-A,k); 28 if(m+k <= C) dp(n,0,m+k); 29 else dp(n,m+k-C,C); 30 31 dp(n,m,C); 32 if(n+k <= A) dp(n+k,m,0); 33 else dp(A,m,n+k-A); 34 if(m+k <= B) dp(n,m+k,0); 35 else dp(n,B,m+k-B); 36 } 37 38 int main(){ 39 while(scanf("%d%d%d",&A,&B,&C) != EOF){ 40 memset(d,0,sizeof(d)); 41 memset(vis,0,sizeof(vis)); 42 dp(0,0,0); 43 int ans = 0; 44 for(int i = 1;i <= A+B+C;i++) 45 if(vis[i]) ans++; 46 printf("%d\n",ans); 47 } 48 return 0; 49 }