【USACO 2018 December Bronze】Back and Forth题解
题目描述
Farmer John有两个挤奶棚,每个挤奶棚里各有一个奶罐和一个装有10个各种尺寸的桶的储物柜。他喜欢将在两个挤奶棚之间来回运送牛奶作为一种锻炼方式。
周一,Farmer John量了恰好1000加仑的牛奶放在第一个挤奶棚的奶罐里,又量了恰好1000加仑的牛奶放在第二个挤奶棚的奶罐里。
周二,他从第一个挤奶棚里取出一个桶,并装满牛奶,然后将牛奶运到第二个挤奶棚,并将牛奶倒进奶罐。他把这个桶留在了第二个挤奶棚。
周三,他从第二个挤奶棚里取出一个桶(可能是周二留在这里的),并装满牛奶,然后将牛奶运到第一个挤奶棚,并将牛奶倒进奶罐。他把这个桶留在了第一个挤奶棚。
周四,他从第一个挤奶棚里取出一个桶(可能是周三留在这里的),并装满牛奶,然后将牛奶运到第二个挤奶棚,并将牛奶倒进奶罐。他把这个桶留在了第二个挤奶棚。
周五,他从第二个挤奶棚里取出一个桶(可能是周二或周四留在这里的),并装满牛奶,然后将牛奶运到第一个挤奶棚,并将牛奶倒进奶罐。他把这个桶留在了第一个挤奶棚。
此时Farmer John测量了第一个挤奶棚的奶罐里的牛奶。他总共可能得到多少种不同的读数?
输入
输入的第一行包含10个整数,为第一个挤奶棚里初始的桶的容积。输入的第二行也包含10个整数,为第二个挤奶棚里初始的桶的容积。所有桶的容积均在1…100的范围内。
输出
输出Farmer John在周五之后测量第一个挤奶棚里的奶罐的牛奶时可能得到的读数的数量。
样例输入
1 1 1 1 1 1 1 1 1 2
5 5 5 5 5 5 5 5 5 5
样例输出
5
提示
在这个例子中,最后第一个挤奶棚的奶罐中的牛奶量总共有5种可能的结果:
1000:FJ可以在每次往返的时候都携带同一个桶,从而不会改变第一个挤奶棚的奶罐的牛奶量。
1003:FJ可以在周二运送2个单位,周三5个单位,周四1个单位,周五1个单位。
1004:FJ可以在周二运送1个单位,周三5个单位,周四1个单位,周五1个单位。
1007:FJ可以在周二运送1个单位,周三5个单位,周四2个单位,周五5个单位。
1008:FJ可以在周二运送1个单位,周三5个单位,周四1个单位,周五5个单位。
思路:
不是我说,这仍然还是水题一道。
看到如此小的数据,看到这求总数的题,一看就想到用搜索。
题目大意:
两个地方各有1000的牛奶,和10个桶。执行4次操作:
- 他从第一个挤奶棚里取出一个桶,并装满牛奶,然后将牛奶运到第二个挤奶棚,并将牛奶倒进奶罐。他把这个桶留在了第二个挤奶棚。
- 他从第二个挤奶棚里取出一个桶(可能是1.留在这里的),并装满牛奶,然后将牛奶运到第一个挤奶棚,并将牛奶倒进奶罐。他把这个桶留在了第一个挤奶棚。
- 他从第一个挤奶棚里取出一个桶(可能是2.留在这里的),并装满牛奶,然后将牛奶运到第二个挤奶棚,并将牛奶倒进奶罐。他把这个桶留在了第二个挤奶棚。
- 他从第二个挤奶棚里取出一个桶(可能是1.或3.留在这里的),并装满牛奶,然后将牛奶运到第一个挤奶棚,并将牛奶倒进奶罐。他把这个桶留在了第一个挤奶棚。
求最后第一个地方可能有的牛奶数量的总数。
解题:
搜索了解一下。
我们用t[i][j]表示i这个位置的第j个桶,每次枚举i这个位置的全部桶(本来就有10桶,最多加2个,总共最多12个)。
按顺序枚举1~ 2,2 ~1, 1~2, 2~1,每次记得把用的桶加到另一个地方的11,12,的空位里,还要删掉原来的值。
最后,判断第一个地方可能有的牛奶数量,没出现过就ans++。
然后……额……没了。
相关文章
- 【论文阅读】SyncPerf: Categorizing, Detecting, and Diagnosing Synchronization Performance Bugs
- ROS2机器人编程简述humble-第三章-BUMP AND GO BEHAVIOR IN PYTHON .4
- MIT 6.828 操作系统工程 2018 fall lab1 part3 内核 笔记 and 中文注释源代码阅读
- ORA-29840: indextype and implementation type are not in same schema ORACLE 报错 故障修复 远程处理
- ORA-01854: julian date must be between 1 and 5373484 ORACLE 报错 故障修复 远程处理
- Unifying ofbiz and MySQL: A Comprehensive Overview(ofbizmysql)
- MySQL and Mango Combination: A Delicious Database Solution(mysqlmango)
- hardLinux: A Journey of Hard Work and Dedication(linuxwork)
- MySQL Errors:Troubleshooting and Solutions(mysqlerrors)
- lsOracle DDLS: Database Development and Design Made Easy(oracledd)
- 深入浅出:MySQL中AND和OR运算符使用方法(mysql中and和or)
- Exploring Redis: Understanding and Managing Current Connection Count(redis当前连接数)
- Mastering MySQL with Vim: Tips and Tricks for Efficient Database Management(mysqlvim)
- MySQL中的AND和OR使用逻辑运算符优化查询语句(mysql中and与or)
- and的区别Oracle数据库中的OR与AND的差异(oracle中or和)
- Oracle中使用AND运算符的示例分析(oracle中and用法)