#include <stdio.h>
#include <stdlib.h>
int n;
static int visited[20];
static int stack[20];
int top;
int prime[38] = 
{0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1};
void dfs (int i,int top)
{
stack[top] = i;
if (top == n - 1)
{
for (int m = 2; m <= n; m ++)
{
if (prime[stack[top] + m] && prime[m + 1] && !visited[m])
{
stack[top + 1] = m;
//printf ("%d\n",m);
for (m = 1; m <= n; m ++)
{
printf (m == 1 ? "%d" :" %d", stack[m]);
}
printf ("\n");
}
}
}
else
{
for (int j = 1; j <= n; j ++)
{
if (prime[i + j] && !visited[j])
{
visited[j] = 1;
dfs (j,top+1);
visited[j] = 0;
}
}
}
}
int main ()
{
int cn = 0;
while ( scanf ("%d", &n) != EOF )
{
printf ("Case %d:\n",++ cn);
visited[1] = 1; top = 1;
dfs (1,top);
printf ("\n");
}
return 0;
}
posted @
2010-08-18 14:25 雪黛依夢(mèng) 閱讀(434) |
評(píng)論 (0) |
編輯 收藏
//這個(gè)題目如果用普通的求模求余方法做一定會(huì)超時(shí)的
//關(guān)鍵是發(fā)現(xiàn)數(shù)字的規(guī)律，當(dāng)位數(shù)之和 > 10 時(shí) 其實(shí)減去 9 就是位數(shù)之和
//采用字符輸入便于求和計(jì)算，同時(shí)處理了大數(shù)問(wèn)題
數(shù)組應(yīng)開(kāi)的比較大
1#include <stdio.h>
2#include <stdlib.h>
3
4int main ()
5{
6 char s[999];
7
8 int i , sum;
9
10 while (scanf ("%s",s) && s[0] != '0')
11 {
12 for (i = sum = 0; s[i]; i ++)
13 {
14 sum += s[i] - '0';
15 }
16
17 printf ("%d\n", sum%9 == 0 ? 9 : sum %9);
18 }
19 return 0;
20}
21
posted @
2010-08-16 11:37 雪黛依夢(mèng) 閱讀(169) |
評(píng)論 (0) |
編輯 收藏
//解題思路：每一個(gè)立方體必然有 3 個(gè)面積，所以 N 種類型的立方體，必然有 3 * N 個(gè)面積組合
//將所有的面積從小到大排列之后，每組面積必然對(duì)應(yīng)一個(gè)高的值，依據(jù)題意，要使高之和最大，所
//以這個(gè)問(wèn)題就轉(zhuǎn)化成了求最長(zhǎng)子列和的最大值
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5//定義一個(gè)結(jié)構(gòu)體存立方體的面積 和 邊長(zhǎng)
6struct cube
7{
8 int x;
9 int y;
10 int z;
11 int area;
12}b[200]; //結(jié)構(gòu)體變量
13
14//這是調(diào)用qsort 函數(shù)時(shí)必須要用的
15int compare(const void* a,const void* b)
16{
17 return (*(cube *)a).area-(*(cube *)b).area; //如果 < 則返回負(fù)數(shù) 如果 = 則返回0 如果 > 則返回 1
18}
19
20// 判斷上面的兩條邊都要 < 下面的兩條邊
21int com (cube a, cube b)
22{
23
if ( (a.x < b.x && a.y < b.y) || (a.y < b.x && a.x < b.y) ) 如：10 20 與 40 50
24
return 1;
25
26
else
27
return 0;
28
}
29
30int main ()
31{
32 int sum[200];
33
34 //用來(lái)控制下標(biāo)的
35 int dir[3][3] = { {0, 1, 2}, {0, 2, 1}, {1, 2, 0} };
36
37 int n;
38 int a[3];
39 int count = 0;
40 while (scanf ("%d", &n))
41 {
42 if (!n)
43 break;
44 int num = 0;
45 memset (sum, 0, sizeof (sum));
46 for (int i = 0; i < n; i ++)
47 {
48 scanf ("%d%d%d", &a[0], &a[1], &a[2]); //讀入輸入的三個(gè)數(shù)據(jù)
49
50 for (int j = 0; j < 3; j ++) //將所有可能的 立方體構(gòu)成 存入到數(shù)組 b 中
51 {
52 b[num].x = a[ dir[j][0] ];
53 b[num].y = a[ dir[j][1] ];
54 b[num].z = a[ dir[j][2] ];
55 b[num].area = b[num].x * b[num].y;
56 num ++; //錯(cuò)點(diǎn)
57 }
58
59 }
60
61 //對(duì) b 數(shù)組按面積進(jìn)行快速排序
62 qsort (b, n * 3, sizeof (b[0]), compare);
63
64 /**//*
65 測(cè)試排序是否正確
66 for (int i = 0; i < 3 * n; i ++)
67 {
68 printf ("%d\t%d\t%d\t%d\n",b[i].x, b[i].y, b[i].z, b[i].area);
69 }*/
70
71 //在滿足題目條件：上面的兩條邊都要 < 下面的兩條邊的情況下找到最大的高的和
72 sum[0] = b[0].z;
73 for (int i = 1; i < 3 * n; i++)
74 {
75 int temp = 0;
76 for (int j = 0; j < i; j ++)
77 {
78 if ( sum[j] > temp && ( com(b[j],b[i]) ) ) //要比較的高的值 滿足題目的條件 累加求和
79 {
80 temp = sum[j];
81 }
82 }
83 sum[i] = temp + b[i].z;
84
85 //printf ("%d\t",sum[i]);
86 }
87
88 //printf ("\n");
89
90 //輸出高的和
91 int max = -1;
92 for (int i = 0; i < 3 * n; i ++)
93 {
94 if (max < sum[i])
95 max = sum[i];
96 }
97
98 printf ("Case %d: maximum height = %d\n", ++count , max);
99
100 }
101
102 return 0;
103}
104
posted @
2010-08-16 10:03 雪黛依夢(mèng) 閱讀(728) |
評(píng)論 (0) |
編輯 收藏
DP 問(wèn)題的關(guān)鍵在于：如何分解子問(wèn)題以及求得子問(wèn)題的最優(yōu)解
//這題可以看成0,1...n,n+1一共n+2個(gè)終點(diǎn)站包括起始點(diǎn),分別求出到達(dá)每個(gè)站的最短時(shí)間即可
//第 i 站時(shí)用前面的timeT[i - 1] + 后面的可能解，由于timeT保存的是到該站時(shí)的最短時(shí)間，所以不斷遞歸 i 之至 n 就可以求得最優(yōu)解
//dp[i]=dp[i-1]+f(i-1,i)(即i-1,到i的最短時(shí)間)
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int L;
int N, C, T;
int vr, vt1, vt2;
int p[103]; //記錄各站p[i]到起點(diǎn)的距離
double timeT[103]; //記錄第i段的最短時(shí)間
double timeR;
while ( scanf ("%d",&L) != EOF )
{
scanf ("%d%d%d", &N , &C, &T);
scanf ("%d%d%d", &vr, &vt1, &vt2);
//兔子的時(shí)間
timeR = L * 1.0 / vr;
//記錄各站p[i]到起點(diǎn)的距離
p[0] = 0;
p[N + 1] = L;
for (int i = 1; i <= N; i ++)
{
scanf ("%d", &p[i]);
}
//找到p[i] 到 p[i + 1]段的最短耗時(shí)
timeT[0] = 0; //遞歸出口
double len;
double e, min;
for (int i = 1; i <= N + 1; i ++)
{
min = 9999999.9;
for (int j = 0; j < i; j ++)
{
len = p[i] - p[j];
if (len > C)
e = ( 1.0 * C / vt1 ) + (len - C + 0.0) * 1.0 / vt2 ;
else
e = len * 1.0 / vt1 ;
e += timeT[j];
if (j)
e += T;
if ( e < min)
min = e;
}
timeT[i] = min;
}
if (timeT[N + 1] < timeR)
{
printf ("What a pity rabbit!\n");
}
else
printf ("Good job,rabbit!\n");
}
return 0;
}
posted @
2010-08-15 16:16 雪黛依夢(mèng) 閱讀(273) |
評(píng)論 (0) |
編輯 收藏
//思路：分析易知遞推關(guān)系式：dp[i][j] = （i - r）* r + dp[r][k] // r條自由線和i - r條平行線的交點(diǎn)數(shù) + r條直線本身的交點(diǎn)數(shù)
// dp[i][j]表示 i 條直線可能的交點(diǎn)種數(shù) j = (i - r）* r + dp[r][k]
// r表示自由線的條數(shù)，（i - r）表示平行線的條數(shù)，（i - r）* r 表示平行線和自由線的交點(diǎn)個(gè)數(shù)
// r 可以取 0 -- i - 1 但是這里初始化的緣故循環(huán)時(shí) r 取 1 -- i - 1
// dp[r][k]表示 r 條直線本身的交點(diǎn)個(gè)數(shù)
// max i 條直線最多的交點(diǎn)數(shù)
// 先把i條直線0個(gè)交點(diǎn)的情況初始值為1(這是一定的)，然后若i-r條直線有j個(gè)交點(diǎn)則i條直線必有（i-r）*r+j個(gè)交點(diǎn)，標(biāo)記為 1
// 通過(guò)標(biāo)記為 1 的下標(biāo) j 為 n 取 i 時(shí)的交點(diǎn)數(shù)
本題的巧妙之處在于：將下標(biāo)對(duì)應(yīng)為交點(diǎn)種類輸出，同時(shí)又滿足了從小到大輸出這個(gè)條件
posted @
2010-08-15 10:02 雪黛依夢(mèng) 閱讀(483) |
評(píng)論 (0) |
編輯 收藏
//本題是在 grids 2757的基礎(chǔ)上得到解決的，即找到最大子例的和
// sum[i] 用于存放到 i 位置為止的子序列的和,所以只需要找到前i - 1 中的sum 所存的最大值再加上本身就可以了
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int b[1001];
int n;
__int64 sum[1001]; //用于存放到 i 位置為止 的子序列的和
while (scanf ("%d", &n) && n)
{
for ( int i = 0; i < n;i ++)
{
scanf ("%d", &b[i]);
}
sum[0] = b[0];
for (int i = 1; i < n; i ++) //下面的處理和 grids 2757的處理思想是一樣的，只不過(guò)sum 數(shù)組存的是和值
{
int tempMaxsum = 0;
for (int j = 0; j < i; j ++) //因?yàn)?nbsp;i 之前的和值已經(jīng)存儲(chǔ)在了sum中，
// 所以只需要找到最大的tempMaxSum后再加上 i 位置本身的值就可以了
{
if (b[j] <b[i] && tempMaxsum < sum[j])
{
tempMaxsum = sum[j];
}
}
sum[i] = tempMaxsum + b[i];
}
__int64 max = -1;
for (int i = 0; i < n; i ++)
{
if (max < sum[i])
{
max = sum[i];
}
}
printf ("%I64d\n",max);
}
return 0;
}
posted @
2010-08-14 21:35 雪黛依夢(mèng) 閱讀(783) |
評(píng)論 (0) |
編輯 收藏
//動(dòng)態(tài)規(guī)劃題目最重要的一點(diǎn)是如何將問(wèn)題分解得到子問(wèn)題，并且將子問(wèn)題解決
//本題以下標(biāo)為狀態(tài)量，找到以該下標(biāo)位置 i 為終點(diǎn)時(shí)的最長(zhǎng)子列：如果 i 位置的值 > i - 1位置的值，則長(zhǎng)度加 1 ，
//所以利用判斷大小來(lái)遞歸，出口是：下表為 0 時(shí)，長(zhǎng)度為 1
//利用 nMaxLen【i】記錄長(zhǎng)度避免了重復(fù)計(jì)算
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{
int n;
int b[1000];
int nMaxLen[1000];
while (scanf ("%d", &n) != EOF && 1 <= n && n <= 1000)
{
memset (nMaxLen, 0 ,sizeof(nMaxLen));
//將輸入的數(shù)值存入數(shù)組 b 中
for (int i = 0; i < n; i ++)
{
scanf ("%d", &b[i]);
}
//找到每一個(gè)狀態(tài)下標(biāo) i 對(duì)應(yīng)的最大子列長(zhǎng)度，并將其存入數(shù)組nMaxLen[]中
nMaxLen[0] = 1;
for (int i = 1; i < n; i ++)
{
int temp = 0;
for (int j = 0; j < i ; j ++)
{
if ( b[i] > b[j])
{
if (temp < nMaxLen[j]) //只有當(dāng)當(dāng)前的長(zhǎng)度 < 之前一位數(shù)的序列長(zhǎng)時(shí)才可以賦值，最后起到 temp + 1 的作用
// 為什么:最大序列可能出現(xiàn)在 j 之后如： 7 9 10 6 11
temp = nMaxLen[j];
}
}
nMaxLen[i] = temp + 1;
}
//遍歷數(shù)組nMaxLen從中讀出最大值，即：在該位置時(shí)取得最大的子序列
int max = -1;
for (int i = 0; i < n; i ++)
{
if (nMaxLen[i] > max)
max = nMaxLen[i];
}
printf ("%d\n", max);
}
//system ("pause");
return 0;
}
posted @
2010-08-14 15:38 雪黛依夢(mèng) 閱讀(208) |
評(píng)論 (0) |
編輯 收藏/*解題思路和1297類似：都是通過(guò)遞推第 n --- 1 種情況合法與不合法，從而知道第 n 種
如下：
設(shè)lock[i]表示：有 i個(gè)槽的鑰匙的個(gè)數(shù)
設(shè)one[i]表示：有 i個(gè)槽且左邊第一個(gè)槽深度為1的鑰匙的個(gè)數(shù)
設(shè)two[i]表示：有 i個(gè)槽且左邊第一個(gè)槽深度為2的鑰匙的個(gè)數(shù)
..
..
設(shè)six[i]表示：有 i個(gè)槽且左邊第一個(gè)槽深度為6的鑰匙的個(gè)數(shù)
則顯然：lock[i]=one[i]+two[i]+ three[i]+four[i]+five[i]+six[i]
由于易知：one[i]=six[i],two[i]=three[i]=four[i]=five[i]
則可以得到：lock[i]=one[i]*2+two[i]*4
當(dāng)左邊第一個(gè)鑿深是1 或 2 時(shí) 與后面的 i - 1 種不合法的情況結(jié)合必須構(gòu)成合法的，由此遞推開(kāi)來(lái)
其中：
one[i]=one[i-1]+two[i-1]+three[i-1]+four[i-1]+five[i-1]+a[i]; //可理解為所有LOKE（i-1）前加1,
所以后面的不能出現(xiàn)six【i - 1】，否則1 6相鄰
=one[i-1]+two[i-1]*4 +a[i] //而a[i]即為不成立的LOKE(i-1)，b[i]同理
two[i]=one[i-1]*2+two[i-1]*4 +b[i]
其中，a[i] 和b[i]的含義分別是：
a[i]表示“有 i個(gè)槽且左邊第一個(gè)槽深度為1，同時(shí)這種鑰匙在除掉第一個(gè)槽后不再是鑰匙”的鑰匙的個(gè)數(shù)。
例如 123,124,125,134,135,145,126,136,146,156 就屬于這種情況。
b[i]表示“有 i個(gè)槽且左邊第一個(gè)槽深度為2，同時(shí)這種鑰匙在除掉第一個(gè)槽后不再是鑰匙” 的鑰匙的個(gè)數(shù)。
分析到這里，可以知道，關(guān)鍵的是求a[i]和b[i]，我們可以得到如下表達(dá)式：
a[i]=(2^(i-1)-2)*6+(2^(i-2)-1)*4
b[i]=(2^(i-1)-2)*9
其中，a[i] 的各部分的含義如下：
(2^(i-1)-2)*6：
當(dāng)去掉第一位，后面i-1位只有 (2,3)或者 (2,4) 或者(2,5) 或者(3,4) 或者(3,5) 或者(4,5)兩種數(shù)字的時(shí)候，
顯然是不合法的鑰匙（不滿足至少有3個(gè)不同的深度），加上第一位的1則顯然是一個(gè)合格的鑰匙。所以后面的數(shù)
字可以為一個(gè)組合中兩個(gè)數(shù)字的任意一個(gè)，根據(jù)乘法原理i-1位一共有2^(i-1)種組合，當(dāng)然還需要去掉兩種特殊
情況，就是后面i-1位完全相同的情況。滿足這種條件的一共有上面六種組合，所以得到(2^(i-1)-2)*6。
(2^(i-2)-1)*4：
當(dāng)去掉第一位，后面i-1位只有 (2,6)或者 (3,6) 或者(4,6) 或者(5，6)兩種數(shù)字的時(shí)候，顯然是不合法的鑰匙
（不滿足至少有3個(gè)不同的深度），加上第一位的1則“可能”是一個(gè)合格的鑰匙。因?yàn)橐⒁鉂M足“相連的槽其
深度之差不得為5”這個(gè)條件，所以，緊跟著1的絕對(duì)不能是6，這樣，相對(duì)于上面的分析，后面i-2位可以是每組
中的任意一個(gè)，所以有2^(i-2)，還要減去1是因?yàn)橥瑯右懦竺嫒渴呛偷?位一樣的數(shù)字這樣的情況。滿足
這種條件的一共有上面的四種組合，所以得到(2^(i-2)-1)*4。
b[i] 的含義如下：
(2^(i-1)-2)*9：
當(dāng)去掉第一位，后面i-1位只有 (1,3)或者 (1,4) 或者(1,5) 或者(3,4) 或者(3,5) 或者(3,6) 或者(4,5) 或者(4,6)
或者(5,6) 兩種數(shù)字的時(shí)候，顯然是不合法的鑰匙（不滿足至少有3個(gè)不同的深度），加上第一位的1則顯然是一個(gè)合
格的鑰匙。所以后面的數(shù)字可以為一個(gè)組合中兩個(gè)數(shù)字的任意一個(gè)，根據(jù)乘法原理i-1位一共有2^(i-1)種組合，當(dāng)然
還需要去掉兩種特殊情況，就是后面i-1位完全相同的情況。滿足這種條件的一共有上面9種組合，所以得到(2^(i-1)-2)*9。
（排除(1,6)是因?yàn)檫@樣的不合法情況和前面的第一個(gè)鑿 2 相結(jié)合后組成的鑰匙還是不合法的）
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
__int64 Lock[26]; //鑿深為 i 時(shí)的可能鑰匙種類
__int64 one[26]; //當(dāng)左邊第一個(gè)鑿深為 1 時(shí)的可能鑰匙種類
__int64 two[26]; //當(dāng)左邊第一個(gè)鑿深為 2 時(shí)的可能鑰匙種類
__int64 a[26]; //當(dāng)左邊第一個(gè)鑿深為 1 時(shí),后面的 i - 1 中可能的不合法情況
__int64 b[26]; //當(dāng)左邊第一個(gè)鑿深為 1 時(shí),后面的 i - 1 中可能的不合法情況
int main ()
{
one[3] = 16;
two[3] = 18;
Lock[3] = 104;
for (int i = 4; i < 26; i ++)
{
a[i] = 16 * (pow (2, i - 2) - 1);
b[i] = 9 * (pow (2, i - 1) - 2);
one[i] = one[i - 1] + 4 * two[i - 1] + a[i];
two[i] = 2*one[i - 1] + 4 * two[i - 1] + b[i];
Lock[i] = 2 * one[i] + 4 * two[i];
}
for (int i = 3;i < 26; i ++)
{
printf("N=%d: %I64d\n", i, Lock[i]);
}
system ("pause");
return 0;
}
posted @
2010-08-14 14:01 雪黛依夢(mèng) 閱讀(246) |
評(píng)論 (0) |
編輯 收藏//利用aMaxSum來(lái)標(biāo)記該位置坐標(biāo)上的值是否被計(jì)算過(guò)了，如果被計(jì)算了直接利用原來(lái)已經(jīng)存在aMaxSum中的值
//遞歸是一個(gè)比較難以理解的知識(shí)，最好的方法是自己通過(guò)畫(huà)出遞歸調(diào)用圖來(lái)理解中間的過(guò)程
//動(dòng)態(tài)規(guī)劃是以遞歸為基礎(chǔ)的，需要解決的是將遞歸中出現(xiàn)的重復(fù)子問(wèn)題記錄下來(lái)，以減少下次遞歸時(shí)的重復(fù)計(jì)算從而減少時(shí)間復(fù)雜度；
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a[101][101];
int n;
int aMaxSum[101][101];
int max_sum (int r,int j)
{
if ( r == n - 1)
return a[r][j];
if (aMaxSum[r + 1][j] == -1)
aMaxSum[r + 1][j] = max_sum (r + 1, j);
if (aMaxSum[r + 1][j + 1] == -1)
aMaxSum[r + 1][j + 1] = max_sum (r + 1, j + 1);
if ( aMaxSum[r + 1][j] > aMaxSum[r + 1][j + 1])
return aMaxSum[r + 1][j] + a[r][j];
else
return aMaxSum[r + 1][j + 1] + a[r][j];
}
int main ()
{
while ( scanf ("%d", &n) != EOF )
{
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < i+ 1; j ++ )
{
scanf ("%d", &a[i][j]);
}
}
memset (aMaxSum, -1, sizeof (aMaxSum));
int max = max_sum (0,0);
printf ("%d\n", max);
}
return 0;
}
posted @
2010-08-14 10:54 雪黛依夢(mèng) 閱讀(138) |
評(píng)論 (0) |
編輯 收藏
#include <stdio.h>
#include <stdlib.h>
int main ()
{
__int64 mi[50];
mi[0]=0;
mi[1] = 1;
mi[2] = 2;
for (int i = 3; i < 50; i ++)
{
mi[i] = mi[i - 2] + mi[i - 1];
}
int n;
int a, b;
while ( scanf ("%d", &n) != EOF )
{
for (int i = 0; i < n; i ++)
{
scanf ("%d%d", &a, &b);
printf ("%I64d\n",a < b ? mi[b - a]: 0);
}
}
return 0;
}
//關(guān)鍵是弄清楚問(wèn)題的本質(zhì)：因?yàn)檫_(dá)到 b 是有兩條路徑的 由此遞推
posted @
2010-08-13 21:31 雪黛依夢(mèng) 閱讀(236) |
評(píng)論 (0) |
編輯 收藏