题解 P1874 【快速求和】

Gu_Ren · 2019-03-23 15:51:34 · 题解

好像没有p党的题解，我来写一发

本题思路就是枚举加号的符号位置，再把数值加起来

我们很容易的可以想到用dfs做，然后加加号，回溯每一个加号位置

但是kkk大佬题解上贡献了另一种思路（用一个数组如s[i,j]表示i到j的数值，变步长的搜索k个加号，k不断递增，判断在k个加号的情况下能否达到所要的值，若能就输出k并退出），不过他没有发代码，就由我来贡献一下代码吧

var
  s1:string;
  s:array[0..41,0..41]of qword;//s[i,j]表示i到j的数值
  i,j,min,x:longint;

 procedure dfs(k,j:longint;sum:qword;num:longint);//k是当前可能要加加号的位置，j是上一次加加号的位置，那么下面的s[j,k]就是j到k的值了，sum和num是当前的数值总和、加号的位置
  begin
    if (num>=min)or(sum>x)or(s[j,k]>x) then exit;//如果加号数不是最少的或总和超过目标要的和就退出，当然如果s[j,k]比目标总和大也要退出
    if k>=length(s1) then //如果能加的加号加完了就把值判断是不是目标数
    begin
      if sum+s[j,k]=x then min:=num;//是的话保存答案
      exit;
    end;
    dfs(k+1,j,sum,num);//当前的位置不加加号
    dfs(k+1,k+1,sum+s[j,k],num+1);//加上加号,并更新j
  end;

begin
  readln(s1);
  readln(x);
  min:=100;
  for i:=1 to length(s1) do
  for j:=1 to length(s1)-i+1 do
  val(copy(s1,i,j),s[i,i+j-1]);//预处理s数组，实现起来还是较容易的，我们可以用pascal的val方便把i到j的数值转换到s[i,j]
  dfs(1,1,0,0);
  if min=100 then write(-1)
  else write(min);
end.

注意总和要开int64/long long