题意：你和一个朋友玩足球游戏，分数从0-0開始，终于你总是赢。而且你主要有两种方式赢，第一种stressFree方式你肯定要进第一个球而且总是比你的朋友分数高，另外一种stressFull方式除了你的朋友达到终于分数时。在游戏中你不可能比你的朋友分数高。
给出一个比分。请分别输出在两种情况下你能赢的方式。
题解：相似于LCS。由于球仅仅能一个一个地进，所以给出终于比分，如果a:b，上一个比分仅仅可能是a-1:b，或者a:b-1。
非常easy写出在stressFree时的动态方程。
1. 设dp_free[i][j]为比分为i:j的全部方式数目。显然i > j。
2. 若i = j+1，则dp_free[i][j] = dp_free[i][j-1]；若i > j+1，则dp_free[i][j] = dp_free[i][j-1]+dp_free[i-1][j]。
相同如果stressFull方式下的最后比分为a：b，则比分肯定是由b:b再全部由你进球所造成的。
1. 设dp_full[i]为你的分数始终不超过你朋友终于分数为i：j的全部方式数目，显然i <= j。
2. 若i = j，则dp_full[i][j] = dp_full[i-1][j]。若i < j。则dp_full[i][j] = dp_full[i-1][j]+dp_full[i][j-1]。
代码例如以下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxN 2005
#define maxP 1000000007
int dp_free[maxN][maxN];
int dp_full[maxN][maxN];
int DP()
{
memset(dp_free,0,sizeof(dp_free));
memset(dp_full,0,sizeof(dp_full));
dp_free[1][0] = 1;
dp_full[0][0] = 1;
for(int i = 0;i < maxN;i++)
{
for(int j = 0;j < maxN;j++)
{
if(i > j)
{
if(j >= 1)
{
dp_free[i][j] = dp_free[i][j-1];
}
if(i >= 1&&i-1 > j)
{
dp_free[i][j] = (dp_free[i][j]+dp_free[i-1][j])%maxP;
}
}
else
{
if(i >= 1)
{
dp_full[i][j] = dp_full[i-1][j];
}
if(j >= 1&&i <= j-1)
{
dp_full[i][j] = (dp_full[i][j]+dp_full[i][j-1])%maxP;
}
}
}
}
return 0;
}
int main()
{
freopen("winning_at_sports.txt","r",stdin);
freopen("out1.txt","w",stdout);
int T;
int a,b;
char c;
DP();
scanf("%d",&T);
for(int i = 1;i <= T;i++)
{
scanf("%d%c%d",&a,&c,&b);
printf("Case #%d: %d %d\n",i,dp_free[a][b],dp_full[b][b]);
}
return 0;
}