HDU1539 Shredding Company(DFS)

题目链接

题意:分割一组数,使这些数组成的新的数组的和不大于给定的数。

#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, l, len, ans, tag, rel;
char s[30];
int path[22], repath[22];
void dfs(int cur, int sum){
    if(sum > n) return;
    if(cur == len){
        if(sum <= n && sum >= ans){
            if(sum == ans) tag = 2;
            else{
                ans = sum, rel = 0, tag = 1;
                for(int i = 0; i < l; i++)
                    repath[rel++] = path[i];
            }
        }
        return;
    }
    int tmp = 0;
    for(int i = cur; i < len; i++){
        tmp = tmp*10 + s[i]-'0';
        path[l++] = tmp;
        dfs(i+1, sum+tmp);
        l--;
    }
}

int main(){
    //freopen("a.txt", "r", stdin);
    while(~scanf("%d%s",&n,s)){
    //while(cin >> n >> s){
        if(n == 0 && s[0] == '0') break;
        memset(path,0,sizeof(path));
        memset(repath,0,sizeof(repath));
        len = strlen(s);
        ans = 0, l = 0, tag = 0;
        dfs(0, 0);
        if(tag == 0) puts("error");
        else if(tag == 2) puts("rejected");
        else{
            cout << ans;
            for(int i = 0; i < rel; i++)
                cout << " " << repath[i];
            cout << endl;
        }
    }
    return 0;
}

题目问题,数组开大一点。

如果这么写:

while(cin >> n >> s){

就WA。。。。。

Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with DFS