Recently Vasya found a golden ticket — a sequence which consists of nn digits a1a2…ana1a2…an . Vasya considers a ticket to be lucky if it can be divided into two or more non-intersecting segments with equal sums. For example, ticket 350178350178 is lucky since it can be divided into three segments 350350 , 1717 and 88 : 3+5+0=1+7=83+5+0=1+7=8 . Note that each digit of sequence should belong to exactly one segment.
Help Vasya! Tell him if the golden ticket he found is lucky or not.
Input
The first line contains one integer nn (2≤n≤1002≤n≤100 ) — the number of digits in the ticket.
The second line contains nn digits a1a2…ana1a2…an (0≤ai≤90≤ai≤9 ) — the golden ticket. Digits are printed without spaces.
Output
If the golden ticket is lucky then print "YES", otherwise print "NO" (both case insensitive).
Examples
Input
5 73452
Output
YES
Input
4 1248
Output
NO
Note
In the first example the ticket can be divided into 77 , 3434 and 5252 : 7=3+4=5+27=3+4=5+2 .
In the second example it is impossible to divide ticket into segments with equal sum.
题意： 给你一串数字，让你判断能不能组成和相等 的几个区间。
这个题目如果不加剪枝会TLE，我用dfs在超时3次后，忽然想起一个事实：就是所求每段的和一定大于等于一串数字中最大的那个数字，比如样例中的73542，每段的和一定大于等于7.
#include<iostream> #include<vector> #include<string> #include<cstring> #include<cmath> #include <algorithm> #include <stdlib.h> #include <cstdio> #include<sstream> #include<cctype> #include <set> #include<queue> #include <map> #include <iomanip> typedef long long LL; const LL INF=0x3f3f3f3f; using namespace std; int ans[102]; int temp[102]; bool flag=0; int T; int M=-0x7ffffff; /*void print() { for(int i=1;i<=T;++i) cout<<temp[i]<<" "; }*/ void dfs(int x,int idx) { if(x>2) { if(temp[x-1]!=temp[x-2]) return ;//一次剪枝，去除序列和不等的情况 } if(flag==1) return ; if(idx==T+1) {flag=1;return ;} int k=0; for(int i=idx;i<=T;++i) { if(x==1&&i==T) return ; k=k+ans[i];//一开始写成k*10+ans[i]..... if(k<M) continue;//关键剪枝：去除不满足条件的情况 temp[x]=k; dfs(x+1,i+1); } } int main() { cin>>T; int a; cin>>a; for(int i=T;i>=1;--i)//先把这串数字离散化，存入数组中 { ans[i]=a; M=max(ans[i],M);//求出最大的那个数字 a/=10; } dfs(1,1); if(flag==1) cout<<"Yes"<<endl; else {cout<<"No"<<endl;} }
