ZOJ 1694 Shredding Company

ZOJ 1694 Shredding Company

碎纸机,给一个带有数字的纸条,把他剪成几块,每块上的数字保持完整,sum为每一块上数字的加和,要求找到小于target的sum的个数,如果没有输出error,如果大于1输出rejected,如果有一个输出剪切的方式.曾经纠结的题目,现在感到不是那么难了..

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>

using namespace std;
int target;
string num;
int mat[10][10];//部分和
int Max,flag[10],reject;
int f[10];//记录最终剪切方式

void dfs( int x,int count )
{
    flag[x] = 1;
    int i;
    if(  x == num.length() )
    {

        if( count == Max && count <= target )
            reject ++;
        if( count > Max && count <= target )
        {
            Max = count;
            reject = 1;
            memcpy(f,flag,sizeof(f));
        }
        flag[x] = 0;
        return;
    }
    for( i = x; i < num.length(); i++ )
        dfs( i+1, count + mat[x][i]);
    flag[x] = 0;
}

int main(void)
{
    int i,j,k,sum;
    while( cin >> target >> num )
    {
        if( !target && num == "0" ) break;

        Max = -1;reject = 0;
        for( i = 0; i < num.length(); i++ )
            for( j = i; j < num.length(); j++ )
            {
                sum = 0;
                for( k = i; k <= j; k++ )
                    sum = sum * 10 + num[k]-'0';
                mat[i][j] = sum;
            }//算出部分和

        memset(flag,0,sizeof(flag));
        dfs( 0,0 );
        if( reject == 0 )//三种情况
            cout << "error" << endl;
        else if( reject > 1 )
            cout << "rejected" << endl;
        else
        {
            cout << Max ;
            for( i = 0; i < num.length(); i++ )
            {
                if( f[i] ) cout << ' ';//每一个切割点都要输出一个空格
                cout << num[i];
            }
            cout << endl;
        }
    }
    return 0;
}