/*
給定一個由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 閱讀(858) |
評論 (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 閱讀(535) |
評論 (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 閱讀(328) |
評論 (0) |
編輯 收藏收藏了很多牛人的技術博客
http://m.shnenglu.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 閱讀(155) |
評論 (0) |
編輯 收藏
Effective C++ 35條,
TR1::functional
posted @
2011-06-15 13:45 nk_ysg 閱讀(315) |
評論 (0) |
編輯 收藏