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];
}