杭州电子科技大学acm 习题精选 第 1 页 共 21 页 目录 1、 数塔问题............................2 2、 并查集类问题........................4 3、 递推类问题..........................9 4、 动态规划系列........................10 5、 概率类题型..........................13 6、 组合数学类题型......................15 7、 贪心策略............................16 8、 几何问题.............................19 杭州电子科技大学acm 习题精选 第 2 页 共 21 页 数塔类问题 数塔 Problem Description 在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？已经告诉你了，这是个DP的题目，你能AC吗? Input 输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。 Output 对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。 Sample Input 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30 #include #include #define MAX 101 int arr[MAX][MAX][2]; void res() { int n; int i,j; memset(arr,0,MAX*MAX*sizeof(int)); scanf("%d",&n); for(i=0;i=0;i--) { for(j=0;j<=i;j++) { if(arr[i+1][j][1]>arr[i+1][j+1][1]) arr[i][j][1]+=arr[i+1][j][1]; else arr[i][j][1]+=arr[i+1][j+1][1]; } } printf("%d\n",arr[0][0][1]); } int main() { int num; scanf("%d",&num); 杭州电子科技大学acm 习题精选 第 3 页 共 21 页 while(num--) { res(); } return 0; } 免费馅饼 Problem Description 都说天上不会掉馅饼，但有一天gameboy 正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来 gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10 米范围内。馅饼如果掉在了地上当然就不能吃了，所以 gameboy 马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只...
