URAL 1437 Gasoline Station

题意:给你三个桶,容量分别为A,B,C,然后问你用这三个没有刻度的桶可以量出多少不同容量的水。0<=A,B,C<=255

一开始认为如果开三维的256^3会跪,但是想不到什么别的好一点的方法,就直接开三维了,结果就过了。这样说来,此题很水。不知道有没有更好的方法。

URAL 1437 Gasoline Station
 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 }
View Code

URAL 1437 Gasoline Station

上一篇:如何帮用户管好云账本?阿里云数据库助力收钱吧 | 甲子光年


下一篇:玩转容器持久化存储第六讲 | 实践:持续集成交付容器环境最佳实践