标签归档：动态规划

小胖办证

1条回复

问题描述
【描述 Description 】

xuzhenyi要办个签证。办证处是一座M层的大楼，1<=M<=100。 每层楼都有N个办公室，编号为1..N(1<=N<=500)。每个办公室有一个签证员。 签证需要让第M层的某个签证员盖章才有效。 每个签证员都要满足下面三个条件之一才会给xuzhenyi盖章： 1. 这个签证员在1楼 2. xuzhenyi的签证已经给这个签证员的正楼下（房间号相同）的签证员盖过章了。 3. xuzhenyi的签证已经给这个签证员的相邻房间（房间号相差1，楼层相同）的签证员盖过章了。 每个签证员盖章都要收取一定费用，这个费用不超过1000000000。 找出费用最小的盖章路线，使签证生效 【输入格式 Input Format 】 第1行两个整数M和N。 接下来M行每行N个整数，第i行第j个数表示第i层的第j个签证员收取的费用。 【输出格式 Output Format】 按顺序打出你经过的房间的编号，每行一个数。 如果有多条费用最小的路线，输出任意一条。 【样例输入 Sample Input 】 3 4 10 10 1 10 2 2 2 10 1 10 10 10 【样例输出 Sample Output】 3 3 2 1 1 【算法分析】 DP顺序：从下到上，再从左到右，再从右到左 【代码】 

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include <stdio.h>
#include <string.h>
#define M 101
#define N 501
int a[M][N], x[M][N], y[M][N], f[M][N];
 
void print(int xx, int yy)
{
       if (xx < 1 || yy < 1)
              return ;
       print(x[xx][yy], y[xx][yy]);
       printf("%d\n", yy);
}
 
int main()
{
 
       int m, n, i, j, min, flag;
       scanf("%d%d", &m, &n);
 
       for (i = 1; i <= m; i++)
       {
              for (j = 1; j <= n; j++)
                     scanf("%d", &a[i][j]);
       }
 
       memset(x, 0, sizeof(x));
       memset(y, 0, sizeof(y));
       memset(f, 0, sizeof(f));
 
       for (j = 1; j <= n; j++)
       {
              f[1][j] = a[1][j];
       }
 
       for (i = 2; i <= m ; i++)
       {
              for (j = 1; j <= n; j++)
              {
                     f[i][j] = f[i - 1][j] + a[i][j];
                     x[i][j] = i - 1;
                     y[i][j] = j;
              }
 
              for (j = 2; j <= n; j++)
              {
                     if (a[i][j] + f[i][j - 1] < f[i][j])
                     {
                            f[i][j] = a[i][j] + f[i][j - 1];
                            x[i][j] = i;
                            y[i][j] = j - 1;
                     }     
              }
 
              for (j = n - 1; j >= 1; j--)
              {
                     if (a[i][j] + f[i][j + 1] < f[i][j])
                     {
                           f[i][j] = a[i][j] + f[i][j + 1];
                            x[i][j] = i;
                            y[i][j] = j + 1;
                     }
              }
       }
 
       min = 2000000000;
 
       for (i = 1; i <= n; i++)
       {
              if (f[m][i] < min)
              {
                     min = f[m][i];
                     flag = i;
              }
       }
 
       print(m, flag);
       return 0;
}

数的划分

发表回复

问题描述
【描述 Description】
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;

问有多少种不同的分法。

【输入格式 Input Format】
输入n，k (6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>
 
int main()
{
 
       int a[201][10] = {0};
       int n, m, i, j;
 
       scanf("%d%d", &n, &m);
       a[0][0] = 1;
 
       for (i = 1; i <= n; i++)
       {
              for (j = 1; j <= m; j++)
                     if (i >= j )
                            a[i][j] = a[i - j][j] + a[i - 1][j - 1];                
       }
 
              printf("%d\n", a[n][m]);
       return 0;
}