题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1745
题目大意：一个串由N个字符组成，每个字符是‘0’或者是‘1’，在任意一段连续的子序列中，要求0和1的个数的差不超过K，求一共有多少种这样的串，比如N=4，K=3时，除了0000和1111外的其他四个字符的串都符合要求。
Sample Input
1 2
4 3
Sample Output
2
14
分析：
这种涉及到任意子区间的性质的问题，如果每个子区间都考虑是很难处理的。注意到0和1的个数之差是满足区间加减法的，也就是说如果我们知道所有后缀的0和1的个数之差那么任意子串的0和1的个数之差也可以间接得出，而在递推的过程中往字符串的末尾中添加字符的时候，会改变的只有所在的后缀——完美的动规出发点。（不明白...）
dp[i][a][b]代表长度为i，所有后缀中1的个数减去0的个数的最大值为a；0的个数减去1的个数最大为b的字符串的种数。注意：后缀包括所谓的空后缀，即a和b的值最小为0。这样所有子串中0的个数和1的个数的差的绝对值最大为a + b。
代码如下：
# include<iostream>
# include<cstdio>
# include<cstring>
# define LL long long
using namespace std;
LL dp[][][],ans; //dp的第二维第三维至少是7 int main()
{
int n,k;
int m,i,j;
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(dp,,sizeof(dp));
dp[][][] = ;
for(m=; m<=n; m++)
{
for(i=; i<=k; i++)
{
for(j=; j<=k; j++)
{
if(i+j<=k)
{
dp[m][i+][max(,j-)] += dp[m-][i][j];
dp[m][max(,i-)][j+] += dp[m-][i][j];
}
}
}
}
ans =;
for(i=; i<=k; i++)
for(j=; j<=k; j++)
if(i+j<=k)
ans += dp[n][i][j];
printf("%lld\n",ans);
}
return ;
}