最近对于邓紫棋的泡沫上瘾了，今天终于被老板从梦中给醒过来了，浪费了太多时间，那些网有啥用呢，一定要做有用的事情
Facebook hackerup round 1 problem C
Winning at Sports25 points
Download Input File
In the game of Sports, the object is have more points than the other team after a certain amount of time has elapsed. Scores are denoted by two hyphen-separated integers. For example, scores may include 3-2, 4-1, or 10-0. The first number is how many points you’ve scored, and the second is the number of points scored by the opposing team. You’re very good at Sports, and consequently you always win. However, you don’t always achieve victory the same way every time.
The two most extreme kinds of victory are called stress-free and stressful. In a stress-free victory, you score the first point and from then on you always have more points than your opponent. In a stressful victory, you never have more points than your opponent until after their score is equal to their final score.
Given the final score of a game of Sports, how many ways could you arrange the order in which the points are scored such that you secure a stress-free or stressful win?
Input
Input begins with an integer T, the number of games you’ll play. For each game, there is one line containing the final score of the game in the format described above.
Output
For the ith game, print a line containing “Case #i: “ followed by two space-separated integers, the number of ways you can achieve a stress-free or stressful win, respectively. Since these numbers may be very large, output them modulo 1,000,000,007.
Constraints
1 ≤ T ≤ 100
Since you always win, the first number in any final score will always be larger than the second. Both scores will be non-negative integers not exceeding 2000.
Explanation of Sample
In the third test case, you can get a stress-free win by scoring points 1, 2, and 4, or points 1, 2, and 3. You can get a stressful win by scoring points 2, 4, and 5, or points 3, 4, and 5.
Example input · DownloadExample output · Download
5
2-1
3-1
3-2
10-5
1000-500
Case #1: 1 1
Case #2: 2 1
Case #3: 2 2
Case #4: 1001 42
Case #5: 70047606 591137401
这道题目咋一看是一道组合题，但是夫神提示之后，才发现是DP。现在感觉写个新的DP并没有一开始学算法课那么深奥了，只要递归几乎都是可以转DP，
也就是把状态存下来，关键是设计DP的状态和转移方程，这题转移比较直观，设计状态是A和B的得分，那么f(i, j) 只可能和f(i-1, j) 和f(i, j-1) 产生
瓜葛，比其他的DP要简单。
代码如下：
ULL SFree[maxn][maxn], SFul[maxn][maxn];
int Sa, Sb, T;
int ansa, ansb;
char ch;
ULL MD=1000000007;
void Solve()
{
memset(SFree, 0, sizeof(SFree));
for(int i=0;i<=Sa;i++)
{
for(int j=0;j<=Sb;j++)
{
if(i<=j) continue;
if(i>=1 && j>=1)
SFree[i][j]=(SFree[i-1][j] +SFree[i][j-1])%MD;
else if(j==0 && i>0)
SFree[i][j]=1ULL;
}
}
memset(SFul, 0, sizeof(SFul));
for(int i=0;i<=Sa;i++)
{
for(int j=0;j<=Sb;j++)
{
if(i==0) SFul[i][j]=1ULL;
else if(j==0)
{
if(Sb==0) SFul[i][j]=1ULL;
}
else
{
if(i<=j || j>=Sb)
SFul[i][j] =(SFul[i-1][j]+SFul[i][j-1])%MD;
}
}
}
ansa=SFree[Sa][Sb], ansb=SFul[Sa][Sb];
}
int main()
{
freopen("winning_at_sports-in.txt", "r",stdin);
freopen("winning_at_sports-ifout.txt","w",stdout);
cin>>T;
for(int Ti=1;Ti<=T;Ti++)
{
cin>>Sa>>ch>>Sb;
Solve();
cout<<"Case #"<<Ti<<": "<<ansa<<" "<<ansb<<endl;
}
return 0;
}
stress-free是一路领先，但是处理b=0的时候是特殊的，这点一开始没有考虑到。现在有一个新的处理边界if else的情况，就是用矩阵划分来弄，
例如if(i==0) 就把第一行去掉，else if (j==0) 就是除掉(0,0) 外的第一列元素，然后再else剩下的i>=1 j>=1的元素这样就不太会出错了，嗯，新技能
get, 计算机很注重离散量和逻辑处理，这方面没有高中数学的训练基础，非常弱，再加上本科有没搞ACM，课程要求太低，学的很不认真，课后题没有做几道。
显得更加单薄，但是对于分析递推公式当成数列题来解我还是比较喜欢的，因为毕竟高中数学的中等难度的数列题是非常喜欢的。
Posted by richard爱闹 - 1月 31 2015
如需转载，请注明： 本文来自 Richard