本題思路非常明確：在所有能插入加號的位置枚舉加號是否存在，對于每一種情況，若求得和為n則更新答案。

但是看看數據規模。。。長度<=40，也就是說枚舉的時間最多可達2^39，顯然會T，所以需要剪枝。

剪枝1：若整串拆分為單個數字后求和，所得結果>n，則一定無解。

原因：顯然在一次拆分后，新生成的數字的和不會比未拆分之前的大（不要問我為什么，這是直覺）。

那么對于某個串，它對應的和最小的拆分方案即為：將其拆分為單個數字。

于是乎，整串對應的最小的和都>n，那么就不可能有可行解了。

剪枝2：若將未處理部分作為一個數字與已處理部分相加，所得的和<n，則在此遞歸子樹中一定無解。

原因：類比一下剪枝1，可得：對于某個串，它對應的和最大的拆分方案為：直接將其轉化為數字，即不拆分（不要問我為什么，這也是直覺）。

那么，將未處理部分作為一個數字與已處理部分相加，就是此遞歸子樹中對應和最大的方案。

如果最大的和都<n，那么就不可能有可行解了。

剪枝3：若當前加號數量>=ans，則此遞歸子樹中無更優解。這一點十分顯然。

剪枝4：若將未處理部分拆分為單個數字后與已處理部分求和，所得的和>n，則在此遞歸子樹中一定無解。

原因：同剪枝1。

剪枝5：若找到一個可行解，則此遞歸子樹中無更優解。再搜下去，加號會增多，一定得不到比此可行解更優的解。

實現細節及剪枝位置詳見代碼及注釋。

1 #include<cstdio> 2 #include<cstring> 3 4 using namespace std; 5 6 void dfs(int,int,int); 7 inline int val(int,int); //將某子串轉化為數字 8 inline int min(int,int); 9 inline int qh(int,int); //將某子串拆分為單個數字后求和 10 11 char s[50]; 12 int a[50],l,ans=2147483647,sum=0,n; 13 14 int main(){ 15 scanf("%s",s+1); 16 scanf("%d",&n); 17 l=strlen(s+1); 18 for(int i=1;i<=l;i++){ 19 a[i]=s[i]-'0'; 20 sum+=a[i]; 21 } 22 if(sum>n){ 23 printf("-1\n"); //剪枝1 24 return 0; 25 } 26 else{ 27 dfs(0,0,0); 28 if(ans==2147483647)printf("-1\n"); 29 else printf("%d\n",ans); 30 } 31 32 return 0; 33 } 34 35 void dfs(int res,int p,int dep){ //res：已處理部分的和 p：標記已經處理到何處 dep：加號數量 36 int temp=res+val(p+1,l); //將未處理部分作為一個數字與已處理部分相加 37 if(temp<n)return; //剪枝2 38 if(dep>=ans)return; //剪枝3 39 if(res+qh(p+1,l)>n)return; //剪枝4 40 if(temp==n){ //找到可行解 41 ans=min(ans,dep); //更新答案 42 return; //剪枝5 43 } 44 for(int i=p+1;i<l;i++){ 45 temp=res+val(p+1,i); 46 dfs(temp,i,dep+1); 47 } 48 } 49 50 inline int val(int l,int r){ 51 int ans=0; 52 for(int i=l;i<=r;i++)ans=(ans<<3)+(ans<<1)+a[i]; 53 return ans; 54 } 55 56 inline int min(int x,int y){ 57 if(x<y)return x;else return y; 58 } 59 60 inline int qh(int l,int r){ 61 int ans=0; 62 for(int i=l;i<=r;i++)ans+=a[i]; 63 return ans; 64 }

轉載于:https://www.cnblogs.com/running-coder-wfh/p/11163527.html

總結

以上是生活随笔為你收集整理的洛谷T1874 快速求和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。