求问hack#2数据
查看原帖
求问hack#2数据
811458
hang_li楼主2024/3/20 22:42

hack#2到底是什么数据啊?一直过不了。。正确结果应该是-1但是不知道为什么,求大佬教教。 附代码:

#include<iostream>  
#include<cstring>  
#include<string.h>  
using namespace std;  
string s;  
  int n;  
int dp[50][100010];//表示在第i位时达到数字j的最少加号数  
int cal(int l, int r) {//这里求和自然满足题目所说的特殊规则  
    int num = 0;  
    for (int i = l;i <= r;i++) {  
        num *= 10;  
        num += s[i] - '0';  
        //考虑可能超出数据范围  
        if (num > n) {  
            return n + 1;  
        }  
    }  
    return num;  
}  
int main() {  
    memset(dp, 127, sizeof(dp));//memset头文件string.h!!!  
    dp[0][0] = 0;  
    cin >> s >> n;  
    int l = s.length();  
    int a = cal(0, 0);  
    dp[0][a] = 0;//先cin!!!  
    for (int i = 0;i < l;i++) {  
        a = cal(0, i);  
        if (a <= n) {  
            dp[i][a] = 0;  
        }  
    }  
    for (int i = 0;i < l;i++) {  
        for (int j = 0;j < i;j++) {  
            int ll = cal(j + 1, i);  
            for (int d = 0;d <= n;d++) {  
                if (d - cal(j + 1, i) >= 0) {  
                    dp[i][d] = min(dp[i][d], dp[j][d - cal(j + 1, i)] + 1);//这里出现了减号!!!  
                }  
            }  
        }  
    }   
    if (dp[l - 1][n] > n) {  
        cout << -1;  
        return 0;  
    }
    cout << dp[l - 1][n];
}  
2024/3/20 22:42
加载中...