P1874 快速求和题解

NanakoCodamorTulip · 2023-11-05 13:13:21 · 题解

主要详细推导一下转移方程

状态定义：

定义 f_{i,j} 为前 i 个数通过添加加号变成数字 j 所需要添加的最小加号个数

辅助数组 num_{i,j} 为连接 s 到 s_j 的结果

转移方程：

对于f_{i,j}，枚举 i 前面的数 k(1 \le k < i) 为添加加号的位置，这时，把前 i 个数分成了两部分，因为后一部分连接起来的数是已知的，为 num_{i-k+1,i}，要使两部分相加等于 j，前一部分要通过添加最少加号使得相加等于 j-num_{i-k+1,i} ，根据定义，前一部分造成的添加加号最小数为 f_{i-k,j-num_{i-k+1,i}}，连接前后部分，得添加加号数为 f_{i-k,j-num_{i-k+1,i}}+1，则转移方程为f_{i,j}=\min (f_{i,j},f_{i-k,j-num_{i-k+1,i}}+1)。
特判 f_{\operatorname{len}(s),j}> \operatorname{len}(s) 则无解

代码

注意long long

#include<iostream>
#include<string.h>//memset在里面
#define int long long
using namespace std;
char s[51];
int len,n,a[51],num[51][51],f[51][10100];
signed main(){
  scanf("%s%lld",s+1,&n);//从1开始读入s
  for(int i=1;s[i]!='\000';i++)len++;//获取len，可以二分（）
  for(int i=1;i<=len;i++)
      for(int j=i;j-i<=11&&j<=len;j++)//答案范围确定j-i<=11
          num[i][j]=num[i][j-1]*10+s[j]-'0';
  memset(f,0x3f,sizeof(f)),f[0][0]=0;
  for(int i=1;i<=len;i++)
      for(int j=1;j<=min((long long)11,i);j++)//为了min函数所以要强制转换11为long long
          for(int k=num[i-j+1][i];k<=n;k++)
              f[i][k]=min(f[i][k],f[i-j][k-num[i-j+1][i]]+1);
  return 0*printf("%lld",f[len][n]>len?-1:f[len][n]-1);//see you
}

~~写完写篇题解庆祝一下~~

P1874 快速求和 题解

状态定义：

转移方程：

代码

P1874 快速求和题解