/*
给定一个由n行数字组成的数字三角形如下图所示。
试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和
对于给定的由n行数字组成的数字三角形，
编程计算从三角形的顶至底的路径经过的数字和的最大值
*/
#include <stdio.h>
#include <string.h>
const int MAXN = 100 + 10;
int a[MAXN][MAXN],d[MAXN][MAXN];
int n;
inline int max(int a,int b) { return a > b ? a : b;}
int dfs(int i,int j)
{
if (d[i][j] >= 0) return d[i][j];
return d[i][j] = a[i][j] + (i == n ? 0 : max(dfs(i+1,j),dfs(i+1,j+1)));
}
int main()
{
int i;
int j;
freopen("1.txt","r",stdin);
while (scanf("%d",&n) != EOF)
{
memset(d,-1,sizeof(d));
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= i; ++j)
scanf("%d",&a[i][j]);
}
printf("%d\n",dfs(1,1));
}
return 0;
}
#include <stdio.h>
const int MAXN = 100 + 10;
int a[MAXN][MAXN],d[MAXN][MAXN];
int n;
inline int max(int a, int b) { return a > b ? a : b; }
int main()
{
int i,j;
freopen("1.txt","r",stdin);
while (scanf("%d",&n) != EOF)
{
for (i = 1; i <= n; ++i)
for (j = 1; j <= i; ++j)
scanf("%d",&a[i][j]);
for (j = 1; j <= n; j++) d[n][j] = a[n][j];
for (i = n - 1; i >= 1; i--)
for (j = 1; j <= i; j++)
d[i][j] = a[i][j] + max(d[i+1][j],d[i+1][j+1]);
printf("%d\n",d[1][1]);
}
return 0;
}
posted @
2011-10-08 01:24 nk_ysg 阅读(829) |
评论 (0) |
编辑 收藏 1 /*
2 输入正整数k,找到所有的正整数x>=y,使得1/k = 1/x + 1/y.
3 样例输入:
4 2
5 12
6 样例输出
7 2
8 1/2=1/6+1/3
9 1/2=1/4+1/4
10
11 8
12 1/12 = 1/156 + 1/13
13 1/12 = 1/84 + 1/14
14 1/12 = 1/60 + 1/15
15 1/12 = 1/48 + 1/16
16 1/12 = 1/36 + 1/18
17 1/12 = 1/30 + 1/20
18 1/12 = 1/28 + 1/21
19 1/12 = 1/24 + 1/24
20 */
21 #include <stdio.h>
22
23 const int MAXN = 1000 + 10;
24 int x[MAXN],y[MAXN];
25
26 int main()
27 {
28 int k;
29 int ans;
30 int i;
31 while (scanf("%d",&k) != EOF)
32 {
33 ans = 0;
34 for (i = k + 1; i <= 2*k; ++i)
35 {
36 if ((k * i) % (i-k) == 0) { x[ans] = (k*i)/(i-k),y[ans++] = i; }
37 }
38 printf("%d\n",ans);
39 for (i = 0; i < ans; ++i)
40 {
41 printf("1/%d = 1/%d + 1/%d\n",k,x[i],y[i]);
42 }
43 }
44 return 0;
45 }
46
posted @
2011-10-07 17:04 nk_ysg 阅读(519) |
评论 (0) |
编辑 收藏
Genealogical tree. 家谱树 Time Limit: 1 second Memory Limit: 16M
Background 大意：火星人的种族关系比较混乱。宗族管理委员会进行开会发言等活动时，又想遵守先长辈，后晚辈的顺序。 于是有下面的问题：
Problem 编写一个程序对给定的人员，决定一个先后顺序， 这个顺序必须遵守先长辈，后晚辈的原则。
Input 首行为N， 1 <= N <= 100 ,N为总人数。根据百年传统，给人员用自然数编号为1至N。以下的N行，第I行为第I个人的子孙列表，子孙的顺序是任意的，用空格隔开，且以0为结束。子孙列表可以是空的。
Output 在一行内输出发言的顺序。 如有多个顺序满足条件，则输出任一个。至少会有一个满足的顺序的。
Sample Input
5 0 4 5 1 0 1 0 5 3 0 3 0
Sample Output
2 4 5 3 1
/* URAL 1022 Genealogical tree
* 900803 09:04:18 21 Aug 2005 RoBa 1022 C++ Accepted 0.001 190 KB
* 拓扑排序
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int MAX = 101;
int map[MAX][MAX],inde[MAX],taken[MAX];
int main()
{
int i,n,tmp,j;
while (scanf("%d",&n)!=EOF)
{
memset(map,0,sizeof(map));
memset(inde,0,sizeof(inde));
for (i = 1 ; i <= n ; i++)
while (scanf("%d",&tmp),tmp)
{
map[i][tmp] = 1;
++inde[tmp];
}
while (1)
{
for (i = 1 ; i <= n ; i++)
if (inde[i] == 0 && taken[i] == 0) break;
if (i > n) break;
for (j = 1 ; j <= n ; j++)
if (map[i][j])
{
map[i][j] = 0;
--inde[j];
}
taken[i] = 1;
printf("%d ",i);
}
printf("\n");
}
return 0;
}
posted @
2011-10-06 19:19 nk_ysg 阅读(306) |
评论 (0) |
编辑 收藏收藏了很多牛人的技术博客
http://www.cppblog.com/Cunch/archive/2011/08/04/152447.html
http://blog.csdn.net/herm_lib/article/list/2
posted @
2011-08-06 09:20 nk_ysg 阅读(135) |
评论 (0) |
编辑 收藏
Effective C++ 35条,
TR1::functional
posted @
2011-06-15 13:45 nk_ysg 阅读(296) |
评论 (0) |
编辑 收藏