跳至正文

USACO 1.4.4 Mother's Milk

  • OI路程

  这一题经过反复的深思熟虑,使用三元数组作为牛奶桶中的牛奶,可以解决很多不必要的纠纷!这个题目充分体现了数据结构对算法影响力的巨大!如果不使用数组而使用三个变量作为参数传递的话,真的会很麻烦的,虽然程序大致的时间复杂度不会改变,但是其常数项会大大增加!所以这题的数据结构选择十分重要。
  我的思路就是暴力枚举所有牛奶可能的情况,反复搜索,用used[a][c]防止重复搜索。

  这里我还有一个空间的优化,不需要单独为答案开辟一个数组,直接使用防止重复的used二维数组来输出就是,也省去了枚举中很多不必要的判断时间,所以我认为这一招是高明的,我直接使用A和C作为used的下标,那么输出答案的时候就用used[0][..]来进行遍历。
  这一题没有一个Mistack,代码具体如下:
/
LANG: C
ID: yylogoo2
PROG: milk3
/
#include <stdio.h>
#include <string.h>
int limit[3];
int used[21][21];
#define move_to(a, b) do{\
        memcpy(tmp, num, sizeof(tmp));\
        if(sub_move_to(tmp, a, b)){\
                srch(tmp);\
        }\
}while(0)

int sub_move_to(int num[3], int from, int to)
{
        int t;
        if(num[from] == 0 || num[to] == limit[to]){
                return 0;
        }
        t = num[from];
        if(t + num[to] > limit[to]){
                t = limit[to] – num[to];
        }
        num[from] -= t;
        num[to] += t;
        return 1;
}

void srch(int num[3])
{
        int tmp[3];
        if(used[num[0]][num[2]]){
                return;
        }
        used[num[0]][num[2]] = 1;

        move_to(01);
        move_to(10);

        move_to(21);
        move_to(12);

        move_to(20);
        move_to(02);
}

int main(void)
{
        int i, k = 0;
        freopen("milk3.in""r"stdin);
        freopen("milk3.out""w"stdout);
        for(i = 0; i < 3; i++){
                scanf("%d", &limit[i]);
        }
        srch((int [3]){00, limit[2]});
        for(i = 0; i <= 20; i++){
                if(used[0][i]){
                        if(k){
                                printf(" ");
                        }
                        k = 1;
                        printf("%d", i);
                }
        }
        printf("\n");
        return 0;
}

发表回复

您的电子邮箱地址不会被公开。