#2
输入:1030484201800080983466306202006000005226 99999
输出:-1
$k$预处理的时候超$int$了
导致$dp[i-j][p-k[i-j+1][i]]$越界或$for(int p=k[i-j+1][i]; p<=n; p++)$循环次数过多超时
更正(已AC):
```cpp
#include<bits/stdc++.h>
using namespace std;
string s;
int n,len;
int a[65];
int k[65][65];
int dp[65][114514];
int main()
{
cin>>s>>n;
if(n==0){
cout<<0;
return 0;
}
len=s.size();
for(int i=0; i<len; i++) {
a[i+1]=s[i]-'0';
}
for(int i=1; i<=len; i++) {
k[i][i]=a[i];
for(int j=i; j-i<=11&&j<=len; j++) {
k[i][j]=k[i][j-1]*10+a[j];
}
}
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[0][0]=0;
for(int i=1; i<=len; i++) {
for(int j=1; j<=11; j++) {
if(i>=j) {
for(int p=k[i-j+1][i]; p<=n; p++) {
if(k[i-j+1][i] < 0 || k[i-j+1][i]>n)break;
dp[i][p]=min(dp[i][p],dp[i-j][p-k[i-j+1][i]]+1);
}
}
}
}
if(dp[len][n]>len||dp[len][n]==0x3f3f3f3f)cout<<-1;
else cout<<dp[len][n]-1;
return 0;
}
```
by lzy_AC7 @ 2023-10-23 20:36:46
(上文K指k数组,代码中更正是在转移方程上一行加了$if(k[i-j+1][i] < 0 || k[i-j+1][i]>n)break;$)
by lzy_AC7 @ 2023-10-23 20:40:53
@[lzy_AC7](/user/672778) 谢谢过了
by niveKmAI @ 2023-11-05 08:24:37