【POJ】2586 Y2K Accounting Bug 解2 枚举

Memory: 140K  Time: 0MS 
枚举下面这样的5种情况
         "ssssdssssdss",
         "sssddsssddss",
         "ssdddssdddss",
         "sddddsddddsd",

   "dddddddddddd"

#include <stdio.h>
#include <string.h>


long s, d, max;

/************************************
|func:检查此串对应的每个阶段是否满足亏损
|args:串str[k]
|retn:若满足返回1，否则返回0
************************************/
int Check(char str[][12], int k)
{
    int i, j;
    long sum;
    for (i=0; i<8; i++)
    {
        sum = 0;
        for (j=i; j<i+5; j++)
        {
            if (str[k][j] == 's')
            {
                sum += s;
            }
            else
            {
                sum -= d;
            }
        }
        if (sum > 0)
        {
            return 0;
        }
    }
    return 1;
}

int main()
{

        //5中情况对应的s，d的个数，方便求和
    int a[5][2]=
    {
        10, 2,
         8, 4,
         6, 6,
         3, 9,
         0, 12
    },i, j;

    char str[5][12]=
    {
        "ssssdssssdss",
        "sssddsssddss",
        "ssdddssdddss",
        "sddddsddddsd",
        "dddddddddddd"
    };
    while(scanf("%ld %ld", &s, &d) == 2)
    {
        i = 0;
        //初始化最大值
        while(!Check(str, i))
        {
            i++;
        }
        max = a[i][0] * s - a[i][1] * d;

        for (i++; i<5; i++)
        {
            for (j=0; j<2; j++)
            {
                    //符合题目条件并且总和比max大才更新max
                if (Check(str, i) && a[i][0] * s - a[i][1] * d > max)
                {
                    max = a[i][0] * s - a[i][1] * d;
                }
            }
        }

        if (max < 0)
        {
            printf("Deficitn");
        }
        else
        {
            printf("%ldn", max);
        }
    }

    return 0;
}

解1参照另外一篇 ”POJ 2586 Y2K Accounting Bug 解1 贪心

2011-03-26 22:38 发表于百度空间，今搬至CU。