ZOJ3158 【DFS】

题意：

从上往下切割，不能切边缘，然后问你两个差值，要小于给出的值。

思路：

直接爆搜，枚举每一行的劈开位置；

#include<bits/stdc++.h>

using namespace std;

const int N=1e2+10;

const int INF=0x3f3f3f3f;

int n,m;

int sum[N][N];

int ssum,ans;

void DFS(int num,int summ)

{

    int temp;

    for(int i=1;i<m;i++)

    {

        temp=summ+sum[num][i];

        if(num==n)

        {

            ans=min(ans,abs(temp-ssum+temp));

        }

        else

            DFS(num+1,temp);

    }

}

int main()

{

    int flag;

    while(~scanf("%d%d",&n,&m))

    {

        int dd;

        memset(sum,0,sizeof(sum));

        ssum=0;

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=m;j++)

            {

                scanf("%d",&dd);

                ssum+=dd;

                sum[i][j]=sum[i][j-1]+dd;

            }

        }

        scanf("%d",&flag);

        ans=INF;

        DFS(1,0);

        if(ans>flag)

            puts("You'd better buy another one!");

        else

            printf("%d\n",ans);

    }

    return 0;

}

巴特西

ZOJ3158 【DFS】

最新文章

热门文章