現在以上面的第二種情況每種種類個數無限為例，給出模板：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
using namespace std;
// Author: Tanky Woo
// www.wutianqi.com
const int _max = 10001;
// c1是保存各項質量砝碼可以組合的數目
// c2是中間量，保存沒一次的情況
int c1[_max], c2[_max];
int main()
{ //int n,i,j,k;
int nNum; //
int i, j, k;
while(cin >> nNum)
{
for(i=0; i<=nNum; ++i) // ---- ①
{
c1[i] = 1;
c2[i] = 0;
}
for(i=2; i<=nNum; ++i) // ----- ②
{
for(j=0; j<=nNum; ++j) // ----- ③
for(k=0; k+j<=nNum; k+=i) // ---- ④
{
c2[j+k] += c1[j];
}
for(j=0; j<=nNum; ++j) // ---- ⑤
{
c1[j] = c2[j];
c2[j] = 0;
}
}
cout << c1[n] << endl;
}
return 0;
}
|
我們來解釋下上面標志的各個地方：
① 、首先對c1初始化，由第一個表達式(1+x+x2+..xn)初始化，把質量從0到n的所有砝碼都初始化為1.
② 、 i從2到n遍歷，這里i就是指第i個表達式，上面給出的第二種母函數關系式里，每一個括號括起來的就是一個表達式。
③、j 從0到n遍歷，這里j就是只一個表達式里第j個變量，比如在第二個表達式里：(1+x2+x4….)里，第j個就是x2*j.
③ k表示的是第j個指數，所以k每次增i（因為第i個表達式的增量是i）。
④ 、把c2的值賦給c1,而把c2初始化為0，因為c2每次是從一個表達式中開始的
#include <iostream>
using namespace std;
int num1[11111];
int num2[11111];
int main ()
{
int N;
while ( cin >> N , N )
{
for ( int i = 0 ; i <= N; ++ i )
{
num1[i] = 1;
num2[i] = 0;
}
for ( int i = 2; i <= 17; ++ i ) 從第二個表達時開始一直到第n個表達式
{
for ( int j = 0;j <= N; ++ j ) 從這個表達式其中的第j項（0---n）分別和所有可能的面值進行指數相加運算 ，j <= 最大可能的面值
{
for ( int k = 0; k + j <= N; k += i * i )
{
num2[j + k] += num1[j];
}
}
for ( int j = 0; j <= N; ++ j )
{
num1[j] = num2[j];
num2[j] = 0;
}
}
cout << num1[N] << endl;
}
return 0;
}
posted @
2010-08-21 11:24 雪黛依夢 閱讀(332) |
評論 (0) |
編輯 收藏
//1.本題如果不注意剪枝很容易超時，這里有兩處剪枝
//2.深度搜索時主要是處理：1.具體題目中如何定深度，本題以某一個合法位置的四個方向是同一深度所以for 循環中steps + 1
// 2.理解回溯的思想
//HDU 1010
#include <stdio.h>
#include <stdlib.h>
int dir[4][2] = {{0, 1}, {-1, 0}, {0, -1},{1, 0}};
char block[9][9]; //迷宮數組
int si, sj; //入口
int di, dj; //出口
int m, n, t;
int steps;
bool escape;
int DFS (int curx, int cury, int steps)
{
//printf ("%d %d", curx, cury);
if (curx < 0 || curx == 0 || cury < 0 || cury == 0 || curx > m || cury > n) //該路徑位置不合理，此次遞歸結束，但并不是整個遞歸結束
return 0;
if (curx == di && cury == dj && steps == t)
escape = 1;
//奇偶性剪枝
int temp = 0;
temp = (t - steps ) - abs (di - curx) - abs (dj - cury); //處在該位置的深搜是否有可能到達終點
if (temp < 0 || temp & 1) //當temp為奇數時 按位與是 1 ，temp為偶數時 按位是 0
return 0;
if (escape)
return 1;
for (int i = 0; i < 4; i ++)
{
if (block[curx + dir[i][0]][cury + dir[i][1]] != 'X') //因為也可以是D
{
block[curx + dir[i][0]][cury + dir[i][1]] = 'X';
DFS (curx + dir[i][0], cury + dir[i][1], steps + 1);
block[curx + dir[i][0]][cury + dir[i][1]] = '.';
}
}
}
int main ()
{
while ( scanf ("%d%d%d", &m, &n, &t) && (m != 0 && n != 0 && t != 0))
{
getchar ();
int wall = 0;
for (int i = 1; i <= m; i ++)
{
for (int j = 1; j <= n; j ++)
{
scanf ("%c", &block[i][j]);
if (block[i][j] == 'S') //入口坐標
{
si = i;
sj = j;
}
if (block[i][j] == 'D') //出口坐標
{
di = i;
dj = j;
}
if (block[i][j] == 'X')
{
wall ++;
}
}
getchar (); //錯點
}
//printf ("%d %d", si, sj);
/**//*for (int i = 1; i <= m; i ++)
{
for (int j = 1; j <= n; j ++)
{
printf ("%d", block[i][j]);
}
}*/
if ( m * n - wall < t) //剪枝
{
printf ("NO\n");
continue;
}
escape = 0;
steps = 0;
block[si][sj] = 'X';
DFS (si, sj, steps);
if (escape)
printf ("YES\n");
else
printf ("NO\n");
}
system ("pause");
return 0;
}
posted @
2010-08-19 11:20 雪黛依夢 閱讀(505) |
評論 (0) |
編輯 收藏