WISEKING
Wiseking.pas/c/cpp
WISEKINGDOM 有N 个公主和M个侍卫暑假到了，公主们要去度假。为了公主的安全WISEKING 将让侍卫保护公主出行，并且每个公主至少需要两个侍卫；现在WISEKING
想知道一共有多少种分配方案；
请你帮WISEKING 求出一共有多少种方案，并输出。
输入：仅一行，两个数N，M；
输出：方案数ANS；
样例1
Wiseking.in
3 5
Wiseking.out
0
样例2
Wiseking.in
2 7
Wiseking.out
4
样例2说明
第一个公主 第二个公主
2 5
3 4
4 3
5 2
对所有数据N<100,M<=500;
首先深搜是可以实现的，不过时间效率太低！
然后就是动规，我们用f[i][j]表示 i 个公主有 j 个护卫的方案总数，用样例举例
f[2][7]表示2个公主，7个护卫的方案总数，而第一个公主可以有2,3,4,5个公主，那么剩下的就是第二个公主的护卫，可以表示为
f[2][7] <-- f[1][2]和f[1][5]
<-- f[1][3]和f[1][4]
<-- f[1][4]和f[1][3]
<-- f[1][5]和f[1][5]
也就是f[i][j]我们就可以分解为f[1][k]和f[i-1][j-k]，由于f[1][k]只可能有一种方案，所以根据加法和乘法原理，f[i][j]的方案数就可以表示为
f[i][j]=f[i-1][j-2]+f[i-1][j-3]+f[i-1][j-4]+...
这样就可以用递推解决，效率远远低于O(n*m*m)
然后几组极限数据就会发现 int 是存不下的，试着用unsigned long long，测完了发现仍然存不下（和long long的效果一样），就只得了60分
所以就要自己写高精度了
写完了一测，超时了。。。。。。后来分析频繁高精度效率一下子就低了！所以方程要简化
我们再来看看方程f[i][j]=f[i-1][j-2]+f[i-1][j-3]+f[i-1][j-4]+...
既然f[i][j]可以写成f[i-1][j-2]+f[i-1][j-3]+f[i-1][j-4]+....，那么同样f[i][j-1]也可以写成f[i-1][j-3]+f[i-1][j-4]+....
所以方程就可以写成f[i][j]=f[i-1][j-2]+f[i][j-1]
其实用到了排列组合的思想，然后写成高精度，就能AC了
/*
C++ Code
http://blog.csdn.net/jiangzh7
By jiangzh
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
int n,m;
int f[110][510][100];//f[i][j]表示i个公主j个护卫的方案总数
void Plus(int *c,int *a,int *b)
{
c[0]=max(a[0],b[0]);
for(int i=1;i<=c[0];i++)
{
c[i]+=a[i]+b[i];
if(c[i]>=10)
{
c[i+1]++;
c[i]-=10;
}
}
while(c[c[0]+1]>0)c[0]++;
}
void output(int *a)
{
for(int i=a[0];i>0;i--)
printf("%d",a[i]);
}
int main()
{
freopen("Wiseking.in","r",stdin);
freopen("Wiseking.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)f[i][j][0]=1;
for(int j=2;j<=m;j++)f[1][j][1]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=m;j++)
Plus(f[i][j],f[i-1][j-2],f[i][j-1]);
output(f[n][m]);
return 0;
}