题目：Vasya and Golden Ticket
题意：给出一个数字构成的序列，问能否把它划分成几段，使得每一段的和相等。
思路：
dp。令f[j]表示当前段在第j个位置结束每一段的和为i能否成立。
枚举段和i，对于每个j，若存在k使得 sum[j]-sum[k-1]==i 且 f[k-1]==true，则f[j]=true。其中sum为关于序列a的前缀和。
代码：
#include<bits/stdc++.h> using namespace std;#define ll long long #define inf (1<<30) #define read(x) scanf("%d",&x) #define maxn 100int n; int a[maxn+5]; int f[maxn+5];void readin() {
read(n);for(int i=1;i<=n;i++) {
scanf("%1d",&a[i]);a[i]+=a[i-1];} }int main() {
readin();for(int i=0;i<a[n];i++) {
memset(f,0,sizeof(f));f[0]=true;for(int j=1;j<=n;j++) {
for(int k=j;k>=1;k--) {
if(a[j]-a[k-1]==i&&f[k-1]) {
f[j]=true;break;}}}if(f[n]) {
printf("YES");return 0;}}if(!a[n]) printf("YES");else printf("NO");return 0; }