（讲义是老师从哪里转来的，不是我们老师写的……）
第一题path是水题，注意100 100要用long long存
1 #include <stdio.h>
2 long long f[101][101];
3 int main()
4 {
5 int m, n;
6 scanf("%d%d", &m, &n);
7 for (int i = 1; i <= 100; i++)
8 f[i][1] = f[1][i] = 1;
9 for (int i = 2; i <= m; i++)
10 for (int j = 2; j <= n; j++)
11 f[i][j] = f[i - 1][j] + f[i][j - 1];
12 printf("%lld\n", f[m][n]);
13 return 0;
14 }
第二题的path可以在第一题的基础上改进一下，也是道水题
1 #include <stdio.h>
2 #include <string.h>
3 long long f[101][101];
4 bool p[101][101];
5 int main()
6 {
7 memset(p, false, sizeof(p));
8 int m, n, t;
9 scanf("%d%d%d", &m, &n, &t);
10 for (int i = 1, x, y; i <= t; i++)
11 {
12 scanf("%d%d", &x, &y);
13 p[x][y] = true;
14 }
15 f[1][1] = 1;
16 for (int i = 1; i <= m; i++)
17 {
18 for (int j = 1; j <= n; j++)
19 {
20 if (i == 1 && j == 1)
21 continue;
22 if (p[i][j] == true)
23 f[i][j] = 0;
24 else
25 f[i][j] = f[i - 1][j] + f[i][j - 1];
26 }
27 }
28 printf("%lld\n", f[m][n]);
29 return 0;
30 }
第三题maxsum，最长连续子序列和，简单但是基础的dp
1 #include <stdio.h>
2 #define MAXSIZE 1001
3 int f[MAXSIZE], a[MAXSIZE], maxn = -1;
4 int main()
5 {
6 int n;
7 scanf("%d", &n);
8 for (int i = 1; i <= n; i++)
9 cin >> a[i];
10 f[1] = a[1];
11 for (int i = 2; i <= n ; i++)
12 {
13 f[i] = max(f[i - 1] + a[i], a[i]);
14 maxn = f[i] >= maxn ? f[i] : maxn;
15 }
16 printf("%d\n", maxn);
17 return 0;
18 }
第四题最长不降子序列和，也是简单但是基础的dp题。
1 #include <stdio.h>
2 #define MAXSIZE 1001
3 int a[MAXSIZE], f[MAXSIZE];
4 int main()
5 {
6 int n, max = -1;
7 scanf("%d", &n);
8 for (int i = 1; i <= n; f[i] = 1, i++)
9 scanf("%d", a[i]);
10 for (int i = 2; i <= n; i++)
11 for (int j = 1; j <= i - 1; j++)
12 if (a[i] >= a[j] && f[i] < f[j] + 1)
13 f[i] = f[j] + 1;
14 for (int i = 1; i <= n; i++)
15 if (f[i] > max)
16 max = f[i];
17 printf("%d\n", f[n]);
18 return 0;
19 }
合唱队形，经典的dp题，双向的最长不降子序列。
1 #include <stdio.h>
2 #define MAXSIZE 1001
3 int f1[MAXSIZE], f2[MAXSIZE], a[MAXSIZE];
4 int main()
5 {
6 int n;
7 scanf("%d", &n);
8 for (int i = 1; i <= n; f1[i] = 1, f2[i] = 1, i++)
9 scanf("%d", &a[i]);
10 for (int i = 2; i <= n; i++)
11 for (int j = 1; j <= i - 1; j++)
12 if (a[i] > a[j] && f2[i] < f2[j] + 1)
13 f1[i] = f1[j] + 1;
14 for (int i = n - 1; i >= 1; i--)
15 for (int j = n; j >= i + 1; j--)
16 if (a[i] > a[j] && f2[i] < f2[j] + 1)
17 f2[i] = f2[j] + 1;
18 int max = f1[1] + f2[1] - 1;
19 for (int i = 1; i <= n; i++)
20 if (f1[i] + f2[i] - 1 > max)
21 max = f1[i] + f2[i] - 1;
22 printf("%d\n", max);
23 return 0;
24 }
最大的正方形，很基础的dp，但是容易写错，需要仔细的推一下转移方程：f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1
初始化很重要，曾经有一次我错了是因为没写初始化
1 #include <stdio.h>
2 #define MAXSIZE 1001
3 int f[MAXSIZE][MAXSIZE];
4 int min(int a, int b)
5 {
6 if (a > b) return b;
7 return a;
8 }
9 int main()
10 {
11 int m, n, t;
12 scanf("%d%d%d", &m, &n, &t);
13 for (int i = 1; i <= m; i++)
14 for (int j = 1; j <= n; j++)
15 f[i][j] = 1;
16 for (int i = 1, x, y; i <= t; i++)
17 {
18 scanf("%d%d", &x, &y);
19 f[x][y] = 0;
20 }
21 for (int i = 1; i <= m; i++)
22 for (int j = 1; j <= n; j++)
23 if (f[i][j] == 0)
24 continue;
25 else
26 f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
27 int max = -1;
28 for (int i = 1; i <= m; i++)
29 for (int j = 1; j <= n; j++)
30 if (f[i][j] > max)
31 max = f[i][j];
32 printf("%d\n", max);
33 return 0;
34 }
35
资源分配，是个变形的背包问题，在背包九讲中提到过，难度一般。
1 #include <stdio.h>
2 #include <string.h>
3 int f[11][101], profit[11][101];
4 int main()
5 {
6 int m, n;
7 memset(f, 0, sizeof(f));
8 scanf("%d%d", &m, &n);
9 for (int i = 1; i <= n; i++)
10 for (int j = 0; j <= m; j++)
11 scanf("%d", &profit[i][j]);
12 for (int i = 1; i <= n; i++)
13 for (int j = 1; j <= m; j++)
14 for (int k = 0; k <= j; k++)
15 if (f[i][j] < f[i - 1][j - k] + profit[i][k])
16 f[i][j] = f[i - 1][j - k] + profit[i][k];
17 printf("%d\n", f[n][m]);
18 return 0;
19 }
20
posted on 2012-10-04 12:12
某科学的魂魄妖梦 阅读(217)
评论(0) 编辑 收藏 引用