POJ 1416 DFS

题目翻译:

公司现在要发明一种新的碎纸机，要求新的碎纸机能够把纸条上的数字切成最接近而不超过target值。比如，target的值是50，而纸条上的数字是12346，应该把数字切成四部分，分别是1、2、34、6。因为这样所得到的和43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超过50的。（比如1, 23, 4, 和6 就不可以,因为它们的和不如43接近50，而12, 34, 6也不可以，因为它们的和超过50了。碎纸还有以下三个要求：

1、如果target的值等于纸条上的值，则不能切。

2、如果没有办法把纸条上的数字切成小于target，则输出error。如target是1而纸条上的数字是123，则无论你如何切得到的和都比1大。

3、如果有超过一种以上的切法得到最佳值，则输出rejected。如target为15，纸条上的数字是111，则有以下两种切法11、1或者1、11.

你的任务是编写程序对数字进行划分以达到最佳值。

题目翻译转载自：優YoU http://user.qzone.qq.com/289065406/blog/1304031265

思路：

一发暴搜敲上去，就A了。。没发现什么坑

// by SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,minn,sum,len,ans[70],vis[70],flag;

char m[70];

void dfs(int pos,int temp){

    if(temp>n)return;

    if(pos==len+1&&minn<=temp){

        if(minn==temp)flag=1;

        else{

            for(int i=1;i<=len;i++)ans[i]=vis[i];

            minn=temp;flag=0;

        }

    }

    int jy=0;

    for(int i=pos;i<=len;i++){

        jy=m[i]+jy*10;

        vis[i]=1;

        dfs(i+1,temp+jy);

        vis[i]=0;

    }

}

int main(){

    while(scanf("%d%s",&n,m+1)&&n){

        len=strlen(m+1);flag=minn=sum=0;

        for(int i=1;i<=len;i++)m[i]-='0',sum+=m[i];

        if(sum>n){puts("error");continue;}

        dfs(1,0);

        if(flag){puts("rejected");continue;}

        printf("%d ",minn);

        for(int i=1;i<=len;i++){

            printf("%d",m[i]);

            if(ans[i])putchar(' ');

        }

        putchar('\n');

    }

}