问题 A: 皮皮扬爱吃芒果
内存限制：64 MB时间限制：3.000 S
评测方式：文本比较命题人：外部导入
提交：727解决：437
返回比赛提交提交记录
题目描述
有一天，皮皮扬有钱了，就叫上了CC去吃一个榴芒，到了店里的时候，皮皮扬买了M个芒果班戟，她想把这些芒果班戟放在N个盘子里，允许盘子可以不放，不过皮皮扬的思维不好，不知道怎么放这些，现在就需要我们来帮皮皮扬算一下一共有多少种不同的分法？
输入
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
输出
对输入的每组数据M和N，用一行输出相应的K。
样例输入 复制
1 7 3样例输出 复制
8提示
5，1，1和1，5，1 是同一种分法。
这题想了很久没太想明白，知道是递归，但是越想情况越多，越想越复杂，然后看了一道经典例题放苹果，有了思路，或者说记住了思路
这类问题总是要先把边界条件找出来，对于这题来说，没有芒果只有一种方法，盘子都空着，f(0,y)=1;没有盘子就没有放法放，f(x,0)=0;只有一个盘子就只有一个放法f(x,1)=1;
然后从2种情况分析
1 如果芒果数量大于或等于盘子数量，没有空盘子，此时将每个盘子都去掉一个芒果，对结果是没有影响的。则此时f(x,y)的值就是f(x-y,y)加上f(x,y-1)的值，因为题干说允许有盘子不放，f(x,y-1)可以算出1个盘子不放，2个盘子不放，3个不放等等
2 芒果数量小于盘子数量，不管怎么放，都至少有y-x个盘子是空的，直接换成f(x,x)
#include<stdio.h>
long long f(long x, long y)//x表示芒果数量，y表示盘子数量
{
if (x == 0||y==1)return 1;//没有芒果只有一种方法，盘子都空着
else if (y == 0) return 0;//没有盘子就没有放法
else if (x >= y)//如果芒果数量大于或等于盘子数量，没有空盘子，此时将每个盘子都去掉一个芒果，对结果是没有影响的。则此时f(x,y)的值就是f(x-y,y)加上f(x,y-1)的值，因为题干说
return f(x - y, y) + f(x, y - 1); //允许有盘子不放，f(x,y-1)可以算出1个盘子不放，2个盘子不放，3个不放等等
else if (x < y)//芒果数量小于盘子数量，不管怎么放，都至少有y-x个盘子是空的
return f(x, x);
}
int main()
{
int t;
long long n, m;
scanf("%d", &t);
while (t--)
{
scanf("%lld %lld", &m, &n);
printf("%lld\n", f(m, n));
}
return 0;
}
这是在csdn上找到的原图，需要我们求出任意2个城市之间的最短距离。首先我们要用邻接矩阵将图存起来，然后通过遍历城市中转，不断更新邻接矩阵。
#include<stdio.h>
int main()
{
int n, m, a, b, c, e[101][101], inf = 999999999;
scanf("%d %d", &n, &m);
//初始化邻接矩阵
for(int i=1;i<=n;i++)
for (int j = 1; j <= n; j++)
{
if (i == j)e[i][j] = 0;
else e[i][j] = inf;
}
while (m--)
{
scanf("%d %d %d", &a, &b, &c);
e[a][b] = c;
}
for (int k = 1; k <= n; k++)//从顶点1开始，更新2个顶点间的距离为通过顶点1中转后的距离与原来的距离的最小距离
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (e[i][j] > e[i][k] + e[k][j])//如果顶点i到顶点k再到顶点j的距离小于顶点i到顶点j的距离
e[i][j] = e[i][k] + e[k][j];//就更新顶点i到顶点j的最小距离
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
printf("%3d", e[i][j]);
printf("\n");
}
return 0;
}
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12