锐客网

  1. 首页 > it技术 > >

# 2019 GDUT Rating Contest #I G. Back and Forth

题解

2019 GDUT Rating Contest #I G. Back and Forth 题目见 ：
http://codeforces.com/group/NVaJtLaLjS/contest/238166/problem/G
题目大意： 懒了，直接翻译吧：（求饶）
农夫约翰有两个挤奶棚，每个都有一个大牛奶罐和一个储藏室。1010大小不一的桶。他喜欢在两个谷仓之间来回运送牛奶作为锻炼的一种手段。周一，农民约翰准确地测量了10001000在第一个谷仓的储罐里放上一加仑牛奶10001000第二个谷仓的储罐里有一加仑牛奶。
周二，他从第一个谷仓拿起一个桶，装满牛奶，然后把牛奶运到第二个谷仓，然后倒进储藏箱。他把桶留在第二个谷仓。
周三，他从第二个谷仓(可能是他周二离开的那个谷仓)拿出一个桶，装满牛奶，然后把牛奶运到第一个谷仓，然后倒进储藏箱。他把桶留在第一个谷仓。
周四，他从第一个谷仓(可能是他周三离开的那个谷仓)拿出一个桶，装满牛奶，然后把牛奶运到第二个谷仓，然后把牛奶倒进罐里。他把桶留在第二个谷仓。
周五，他从第二个谷仓(可能是他周二或周四留下的那个)拿出一个桶，装满牛奶，然后把牛奶运到第一个谷仓，然后把牛奶倒进罐里。他把桶留在第一个谷仓。
农夫约翰然后在第一个谷仓的罐里量牛奶。他能看到多少不同的读数？
输入
思路： 【# 2019 GDUT Rating Contest #I G. Back and Forth】直接dfs搜索模拟即可。？？快累死了
一次优化： 可以记录一个仓库的奶量记忆化，可以减少大约1/3的搜索量。//好累啊！！！
实现：

#include #include int now=1000; int f[2000],a[21],place[21]; void search(int day) {//printf("%d %d\n",day,now); int i; if (day==6) { f[now]++; return ; } if (day%2==0) { for (i=1; i<=20; i++) if (place[i]==1) { place[i]=2; now-=a[i]; search(day+1); now+=a[i]; place[i]=1; } }else for (i=1; i<=20; i++) if (place[i]==2) { place[i]=1; now+=a[i]; search(day+1); now-=a[i]; place[i]=2; } } int main() { int i,j,n,m,ans=0; for (i=1; i<=20; i++) { scanf("%d",&a[i]); if (i<=10) place[i]=1; else place[i]=2; } for (i=500; i<=1500; i++) f[i]=0; search(2); for (i=500; i<=1500; i++) if (f[i]>0) ans++; printf("%d\n",ans); return 0; }

    推荐阅读


    上一篇：2019 GDUT Winter Personal Training Contest III (Div. 2) A题 QAQ 题解

    下一篇：Flowable实战2-集成Springboot